Pairwise alignment

• Local alignment: The best possible matching substring or subsequence alignment between two strings—based on a substitution matrix and gap penalty function—allowing for gaps and mismatches within a specified region of the input sequences.
  1. Dynamic programming solution¹: $O(nm)$ in terms of space and time. See vizualization
• Global alignment: The best possible alignment between two strings over their entire length.
  1. Dynamic programming solution²: $O(nm)$ in terms of space and time. See vizualization
  2. Divide-and-conquer + dynamic programming solution³: $O(m)$ in terms of space and O(nm) time. See vizualization
• Longest common substring: The longest contiguous substring that appears in both strings.
  1. Dynamic programming solution: $O(nm)$ in terms of space and time.
• Longest common subsequence: The longest possible sequence of symbols that appears in the same order in both strings. See LCS distance.
  1. Dynamic programming solution: $O(nm)$ in terms of space and time.
• Dynamic time warping (DTW): The optimal warp path that minimizes the distance between sequences of varying length.
  1. Dynamic programming solution⁴: $O(nm)$ in terms of space and time.
  2. Space-time improved version of (1) via Hirschberg³ algorithm: Reduces space complexity to $O(m)$.

Taken from: string2string: A Modern Python Library for String-to-String Algorithms

Footnotes

1. T. F. Smith and Michael S. Waterman. 1981. Identification of common molecular subsequences. Journal of molecular biology, 147 1:195–7 ↩

2. Saul B Needleman and Christian D Wunsch. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443–453. ↩

3. Daniel S. Hirschberg. 1975. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341–343. ↩ ↩²

4. Hiroaki Sakoe and Seibi Chiba. 1978. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing, 26(1):43–49. ↩