Local Sequence Alignment Algorithm

A Local Sequence Alignment Algorithm is a Sequence Alignment Algorithm that aligns subsequences by finding similarity regions between subsequences.

• Example(s):
  • Smith-Waterman Algorithm,
  • …
• Counter-Example(s):
  • Global Sequence Alignment Algorithm,
  • BLAST Algorithm,
  • FASTA Algorithm,
  • Karp-Rabin Algorithm,
  • Needleman-Wunsch Algorithm,
  • rawMSA Algorithm,
  • Wagner-Fischer Algorithm.
• See: Approximate String Matching Algorithm, Sequence Homology, Longest Common Subsequence, Shortest Common Supersequence, Longest Common Substring, Shortest Common Superstring, Approximate String Matching, Phylogenetic Analysis Task, Alignment-free Sequence Analysis Task, Levenshtein Distance, Edit Distance, Alignment Distance, Sequential Pattern Mining Task, Dynamic Programming.

---

---

References

2021a

• (Kellis et al., 2021) ⇒ Manolis Kellis et al. (2021). "3.2: Introduction". In: "Book: Computational Biology - Genomes, Networks, and Evolution (Kellis et al.)", LibreTexts.
  • QUOTE: This chapter will address other forms of alignment algorithms to tackle such scenarios. It will first introduce the Smith-Waterman algorithm for local alignment for aligning subsequences as opposed to complete sequences, in contrast to the Needleman-Wunsch algorithm for global alignment. Later on, an overview will be given of hashing and semi-numerical methods like the Karp-Rabin algorithm for finding the longest (contiguous) common substring of nucleotides. These algorithms are implemented and extended for inexact matching in the BLAST program, one of the most highly cited and successful tools in computational biology. Finally, this chapter will go over BLAST for database searching as well as the probabilistic foundation of sequence alignment and how alignment scores can be interpreted as likelihood ratios.

2011b

• (Kellis et al., 2021) ⇒ Manolis Kellis et al. (2021). "3.3: Global alignment vs. Local alignment vs. Semi-global alignment". In: "Book: Computational Biology - Genomes, Networks, and Evolution (Kellis et al.)", LibreTexts.
  • QUOTE: A global alignment is defined as the end-to-end alignment of two strings $s$ and $t$.

    A local alignment of string $s$ and $t$ is an alignment of substrings of s with substrings of $t$.

    In general are used to find regions of high local similarity. Often, we are more interested in finding local alignments because we normally do not know the boundaries of genes and only a small domain of the gene may be conserved. In such cases, we do not want to enforce that other (potentially non-homologous) parts of the sequence also align. Local alignment is also useful when searching for a small gene in a large chromosome or for detecting when a long sequence may have been rearranged (...)

---