Pattern recognition in genetic sequences

作者：Peter H. Sellers · 发表于：Proceedings of the National Academy of Sciences · 年份：1979 · DOI：10.1073/pnas.76.7.3041 · 被引用次数：41 · 研究领域：Machine Learning in Bioinformatics、Fractal and DNA sequence analysis、Algorithms and Data Compression

This paper announces an algorithm for finding pattern similarities between two given finite sequences. Two portions, one from each sequence, are similar if they are close in the metric space of evolutionary distances. In its most general form the algorithm allows a complete list to be made of all pairs of intervals, one from each of the two given sequences, such that each pair displays a maximum local degree of similarity; if the lengths of the sequences are m and n, then the algorithm requires on the order of mn steps. This result lends itself to detecting similarities by computer between pairs of biological sequences, such as proteins and nucleic acids.