6 - Alignments

Summary

An alignment of two sequences A and B aims to highlight how much in common the two sequences have. This concept arises naturally in settings where a sequence A changes over time into B, through some elementary edit operations, such as insertion or deletion of a character (operations called indels), or substitution/mutation of one character with/into another. An alignment of the characters which have survived over time could be defined informally as a list of pairs of indices (i, j), such that A[i] is considered to match B[j].

In a computational biology context, the sequences A and B could be short extracts from the genomes of two living species, fragments considered to have descended from an unknown ancestor sequence C. A biologically meaningful alignment of A and B should take into account the path in the evolutionary tree from A to C and from C to B. However, since in practice C and the evolutionary tree are unknown, then one could parsimoniously prefer an alignment with the minimum number of edit operations.

Taking into account some properties of biological sequences, one can assign different costs to the different edit operations. For example, in a coding region, the substitution of a base is usually less critical than an indel, which alters the synchronization between codons and the amino acid chain under translation. The former is likely to survive in an evolutionary selection, while the latter is not. Therefore, one could assign a high positive cost for indels, some low positive cost for substitutions, and cost 0 for an identity, that is, for two matched characters that are also equal. The biologically meaningful alignment could then be approximated by finding the alignment with minimum total cost. This cost of an optimal alignment is also called the edit distance.

In biological sequence analysis it has been customary to resort instead to a maximization framework, where in place of cost one assigns a score to each operation. The score of an alignment thus becomes a measure of the similarity between two sequences.