An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules 论文

摘要

A wide variety of different applications lead to problems in which sequences of different lengths must be compared, to see how different they are, and to see which elements in one sequence correspond to which elements in the other sequence. Successful methods for handling these problems been repeatedly reinvented which incorporate two basic ideas a systematic concept of distance between sequences, and elegant recursive algorithms for doing the necessary computations. The major application areas are speech processing and macromolecular biology. Computer science is another significant application area, and applications have also been made to bird song, handwriting analysis, gas chromatography, geological strata, and text collation. This paper surveys the applications, methods and theory of sequence comparison.