A TIME-EFFICIENT, LINEAR-SPACE LOCAL SIMILARITY ALGORITHM
A TIME-EFFICIENT, LINEAR-SPACE LOCAL SIMILARITY ALGORITHM
复制标题
DOI：
10.1016/0196-8858(91)90017-d
复制
发表时间：
1991-09-01
影响因子：
1.1
通讯作者：
MILLER, W
中科院分区：
文献类型：
--
作者：
HUANG, XQ;MILLER, W
确定两个序列的相似区域的动态编程算法对于分析生物序列数据非常有用。本文提出了一种省时的算法，可为任何选定的 k 生成 k 最佳“非相交”局部对齐。该算法的主要优点是它只需要O(M+N+K)空间，其中M和N是给定序列的长度，K是计算的比对的总长度。
Dynamic programming algorithms to determine similar regions of two sequences are useful for analyzing biosequence data. This paper presents a time-efficient algorithm that produceskbest “non-intersecting” local alignments for any chosenk. The algorithm's main strength is that it needs onlyO(M+N+K) space, whereMandNare the lengths of the given sequences andKis the total length of the computed alignments.