Lesson 2

Let us give an example of such a result. In the local sequence alignment problem it is required to identify similar segments of two nucleotide or protein sequences. The Smith–Waterman algorithm, based on the dynamic programming method and published in 1981, solves this problem in time \(O(n^{2})\), where \(n\) is the length of the input sequences (if they have different lengths, one can assume that \(n\) is the maximum of the lengths).

This quadratic algorithm turns out to be impractical, since in practice sequences can be several million long. For this reason, in practice heuristic algorithms are often used that work much faster but do not guarantee that the alignment they produce is optimal. As of June 2025, the article about one such tool, BLAST, has more than a hundred thousand citations!