A TIME-EFFICIENT, LINEAR-SPACE LOCAL SIMILARITY ALGORITHM

被引：810

作者：

HUANG, XQ ^{[1
]}

MILLER, W ^{[1
]}

机构：

[1] PENN STATE UNIV,DEPT COMP SCI,UNIVERSITY PK,PA 16802

来源：

ADVANCES IN APPLIED MATHEMATICS | 1991年 / 12卷 / 03期

关键词：

D O I：

10.1016/0196-8858(91)90017-D

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Dynamic programming algorithms to determine similar regions of two sequences are useful for analyzing biosequence data. This paper presents a time-efficient algorithm that produces k best "non-intersecting" local alignments for any chosen k. The algorithm's main strength is that it needs only O(M + N + K) space, where M and N are the lengths of the given sequences and K is the total length of the computed alignments. © 1991.

引用

页码：337 / 357

页数：21

共 14 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] PATTERN-RECOGNITION IN NUCLEIC-ACID SEQUENCES .1. A GENERAL-METHOD FOR FINDING LOCAL HOMOLOGIES AND SYMMETRIES [J].