Article

For closely related sequences there is a single optimal alignment which provides an accurate measure of similarity, structure, function and evolutionary history. However, with increasing evolutionary distances between nucleotide sequences the single optimal alignment method is replaced by an ensemble of alignments of almost equal quality and ensemble of different self-folded conformations.

Recurring difficulties associated with diverged sequence data include alternative alignment possibilities of insertions and deletions, region of length variations in which homology assessment is questionable or impossible, occurrence of localized excessive mutations to the point of saturation and lost of phylogenetic signals. Therefore, for diverged sequences optimizing similarity will not necessarily improve structure, function and evolutionary history assessments. Here our aim is to present an overview of the methods involved in sequence analysis which are critical for current theoretical and application development. However, we do not follow historical events. For sequence comparison we focus on those methods that are based on exhaustive schemes, which are classically formulated as dynamic programming algorithms. They consist either of optimization schemes which find the best alignment for a given model, or of probabilistic schemes based on partition functions - in which all alignments, with their respective weights, are evaluated.