近似字符串匹配算法

好的,Needleman Wunsch(NW)是生物信息学文献中经典的端到端(“全局”)对齐器。很久以前,它在FASTA包中以“align”和“align0”的形式提供。不同之处在于“0”版本在避免端部间隙方面没有那么偏袒,端部间隙通常允许更容易偏好高质量的内部匹配。我想你们应该知道,史密斯·沃特曼是一名当地的校准器,是爆炸的原始基础。FASTA也有它自己的本地定位仪,但有点不同。所有这些基本上都是启发式方法,用于估计与单个字符对评分指标相关的Levenshtein距离(在生物信息学中,通常由Dayhoff/“PAM”给出),Henikoff&Henikoff,或其他矩阵,并且当应用于自然语言时,通常替换为更简单、更合理地反映语言词形替换的内容)。

至于你自己的问题:几年前,我必须对照已知正确的参考序列检查短DNA读取的准确性,我提出了一种我称之为“锚定比对”的方法。

其思想是获取引用字符串集,并通过查找给定N字符子字符串出现的所有位置来“消化”它。选择N,这样您构建的表就不会太大,但长度为N的子字符串也不会太常见。对于像DNA碱基这样的小字母表,可以对N个字符的字符串进行完美的散列,然后创建一个表,并将每个字母表中的匹配项链接到一个链表中。列表条目必须标识子字符串的顺序和起始位置,该子字符串映射到它们出现在其列表中的bin。这些是要搜索的字符串列表中的“锚”,在这些字符串上,NW对齐可能是有用的。

处理查询字符串时,将从查询字符串中某个偏移量K开始的N个字符进行散列,查找其bin,如果该bin的列表为非空,则遍历所有列表记录,并在查询字符串和记录中引用的搜索字符串之间执行对齐。进行这些对齐时,将查询字符串和搜索字符串对齐 锚定并提取搜索字符串的子字符串,该子字符串的长度与查询字符串的长度相同,并且在相同的偏移量K处包含该锚定。

这种方法试图通过限制NW的输入来提高NW,这有一个性能增益,因为您进行的对齐较少,而且它们更多地位于相似序列之间。使用NW对齐器的另一个好方法是,在出现一定数量或长度的间隙后,允许它放弃,以降低成本,特别是当您知道您不会看到或对中等质量的匹配感兴趣时。

无论哪种方式,允许同时使用来自查询字符串不同端的多个锚点可能有助于进一步过滤馈送到NW的数据。如果这样做,请准备好可能将每个包含两个定位点之一的重叠字符串发送到对齐器,然后协调对齐。。。或者可能进一步修改NW,以强调在算法执行期间使用惩罚修改在对齐过程中保持锚点基本完整。

希望这是有益的或至少有趣的。

与Levenstein距离相关:您可能希望通过将结果除以较长字符串的长度来对其进行规范化,以便始终得到一个介于0和1之间的数字,从而可以有意义地比较一对字符串的距离(表达式L(a,B)>L(a,C)-例如-没有意义,除非将距离标准化)。

我们正在使用 Levenshtein distance 方法检查数据库中的重复客户。它工作得很好。

可供选择的算法有 agrep Wikipedia entry on agrep ), FASTA and BLAST 生物序列匹配算法。这些都是特殊情况 approximate string matching Stony Brook algorithm repositry . 如果可以指定字符串彼此不同的方式,则可以将重点放在定制的算法上。例如,aspell使用“soundslike”(soundex变音)距离的一些变体与“键盘”距离相结合,以适应拼写错误和打字错误。

使用 FM Index 具有回溯功能,类似于 Bowtie

为了最大限度地减少由于拼写上的细微变化或错误而导致的不匹配,我使用了变音算法,然后在变音编码上使用Levenshtein距离(以百分比匹配的形式缩放为0-100)来衡量接近度。这似乎效果相当不错。

在Cd-MaN的回答中进一步说明,听起来您面临着一个规范化问题。如何处理长度不同的对齐之间的分数并不明显。

考虑到您感兴趣的内容,您可能希望获得路线的p值。如果您使用的是Needleman Wunsch,则可以使用Karlin Altschul统计信息获得这些p值 http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

BLAST可以进行局部对齐,并使用这些统计信息对其进行评估。如果你关心速度,这将是一个很好的工具使用。

另一个选择是使用HMMER。HMMER使用轮廓隐马尔可夫模型来对齐序列。就个人而言,我认为这是一种更强大的方法,因为它还提供位置信息。 http://hmmer.janelia.org/