Objective Functions

Multiple sequence alignment involves alignment of more than two sequences and is an NP-complete problem. Therefore, heuristic algorithms that use different criteria to find an approximation to the optimal solution are employed. At the heart of these approaches lie the scoring and objective functions that a given algorithm uses to compare competing solutions in constructing a multiple sequence alignment. These objective functions are often motivated by the biological paradigms that govern functional similarities and evolutionary relations. Most existing approaches utilize a progressive process where the final alignment is constructed sequentially by adding new sequences into an existing multiple sequence alignment matrix, which is dynamically updated. In doing this, the core scoring function to assess accuracies of pairwise alignments generally remains the same, while the objective functions used in intermediary steps differ. Nevertheless, the overall assessment of the final multiple sequence alignment is generally calculated by an extension of pairwise scorings. In this chapter, we explore different scoring and objective functions used in calculating the accuracy and optimization of a multiple sequence alignment and provide utilization of these criteria in popularly used multiple sequence alignment algorithms.