我正在寻找以下问题的解决方案：
我确实有一个超过600万行的数据帧，其中一行包含测序信息(DNA序列(。根据数据集的报告方式，数据帧中会有重复的行。但是：这些重复并不是完美匹配。让我用一个例子来说明这一点。
row 1: ATCTCAGCATCATACCAACTACTA
...
row 5: ATCTCAGCATCATA..........
前一个块显示了数据帧的两个不同行中的两个序列。显示这些点只是为了可视化(它们不是数据集的一部分(。
目标是：将这些序列标记为相同。(最后，我的目标是为每一行分配一个序列ID，因此这两行应该具有相同的序列ID，因为第5行中的序列是第1行中序列的一部分，因此序列可能是相同的
我试着使用基本R的match函数或grep的一些尝试，但这些方法都非常非常慢，如果没有失败的话。
我还尝试了一些方法，比如Biostring的将模式字典与引用函数进行匹配，但在创建字典的步骤上我已经失败了，因为这似乎是因为行中序列的长度非常不同。
(来自Biostring的错误消息。(
Error in .Call2("ACtree2_build", tb, pp_exclude, base_codes, nodebuf_ptr, :
element 2 in Trusted Band has a different length than first element
有人知道如何实现我想要实现的目标吗？同样，一个挑战是超过600万行的数据帧的大小，并且基本上是针对数据帧中的每一行测试每一行。
非常感谢您的反馈！真的很感激！
添加信息如果以下假设成立，是否有一种可行的方法：只有当字符串在开头匹配时才感兴趣，并且至少有一个字符串必须与完整的字符序列匹配。换句话说：一行的完整序列可以在一行或多行的字符串开头找到。
以下是我为解决更简单的问题(查找作为其他序列的初始子串的序列(而准备的内容。更普遍的问题可以类似地解决，只是更混乱，需要(更长(时间。在下一步中，我计划模拟您的数据(创建一个包含600万个长度在您提到的范围内的字符串的文本文件(，并测试解决方案，看看它需要多长时间。然后，正如我所说，我将在Oracle数据库中尝试同样的事情，看看是否存在巨大的差异。只有当"简单问题"在合理的时间内运行时，"一般问题"才是合理的项目。
我假设数据具有某种序列标识符(id在数据库中是自然的(。你会在输入文件中看到这一点，我在下面展示了它。您也将看到输出的格式——对于每个较短的序列，即较长序列的初始子串，我将显示这两个序列(及其id(。注-较短的序列，如ACTAGC，可以是多个较长字符串的初始子字符串，如ACTAGCTA和ACTAGCAGCA。我的输出只显示一个较长的序列，而不是所有较长的序列。
原则上，该算法是琐碎的。按字母顺序对所有字符串进行排序，然后只对照下一个字符串检查每个字符串。如果它不是子字符串，那么它就不能是数据集中任何其他字符串的子字符串。其余部分在bash中实现。
对于长度最多为k的n个序列，按字母顺序排列所有序列是O(kn log n)，对照下一个字符串检查每个字符串是O(kn)，这就是为什么这有机会处理600万行的原因。
输入文件：
$ cat input_file
10010 ACATAAGAGTGATGATAGATAGATGCAGATGACAGATG
10011 ATAGAGATGAGACAGATGACAGAAGATAGATAGAGCAGATAG
10013 ATAGAGTAGAGAGAGAGTACAGATAGAGGAGAGAGATAGAC
10015 ACAGATAGCAGATAGACAGA
10016 ACAGATGACAGAAGATAGATAGA
10018 TAAGAGTGATGATAGATAGATGCAGA
10023 ATCACCGTTACAGATCG
10024 GTGATGATAGATAGATGCAGATGACAGATG
10025 ATAGAGTAGAGAGAGAGT
10030 TAAGAGTGATGATAGATAG
10044 TAAGAGTGATGATAGATAGATGCAATGA
编辑-下面的BASH脚本非常愚蠢，向所有人道歉。在这个答案的最后，我将展示正确的方法；使用SED，而不是外壳循环和读取命令
BASH脚本文件名：dupes.sh
#!/bin/bash
sort -k 2 input_file |
{
read key1 seq1
while read key2 seq2
do
if [[ $(expr substr $seq2 1 ${#seq1}) == $seq1 ]]
then
echo ""
echo "$key1 $seq1"
echo "$key2 $seq2"
fi
key1=$key2
seq1=$seq2
done
}
(我使用echo进行输出；您可能希望重定向到一个文件。(
发票和输出
$ ./dupes.sh
10025 ATAGAGTAGAGAGAGAGT
10013 ATAGAGTAGAGAGAGAGTACAGATAGAGGAGAGAGATAGAC
10030 TAAGAGTGATGATAGATAG
10044 TAAGAGTGATGATAGATAGATGCAATGA
编辑-正如我上面所说，虽然这是正确的答案，但解决方案非常糟糕。以下是在bash中执行此操作的正确方法。对于相同数量的输入数据，此解决方案所需时间不到一分钟(！！((而不是80分钟(
sort -k 2 dna_sequences | sed -nE '{N; /^[^ ]+ ([^ ]+)n[^ ]+ 1/p; D}'
输出可以重定向到一个文件，也可以进一步处理(例如，我不会在每个匹配的对之后添加换行符；这可以在输出的进一步处理中完成，或者在必要时通过其他方式完成(。