An efficient algorithm for identifying matches with errors in multiple long molecular sequences.
An efficient algorithm is described for finding matches, repeats and other word relations, allowing for errors, in large data sets of long molecular sequences. The algorithm entails hashing on fixed-size words in conjunction with the use of a linked list connecting all occurrences of the same word. The average memory and run time requirement both increase almost linearly with the total sequence length. Some results of the program's performance on a database of Escherichia coli DNA sequences are presented.
Leung
M Y
MY
Division of Mathematics, Computer Science and Statistics, University of Texas, San Antonio 78249-0664.
Blaisdell
B E
BE
Burge
C
C
Karlin
S
S
D000465:Algorithms; D001483:Base Sequence; D016384:Consensus Sequence / Q000235:genetics; D016208:Databases, Factual; D004926:Escherichia coli / Q000235:genetics; D008969:Molecular Sequence Data; D009154:Mutation / Q000235:genetics; D012091:Repetitive Sequences, Nucleic Acid / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*