Dynamic Programming Algorithms for Biobjective Sequence Alignment

Authors

Abstract

In this work, the multiobjective formulation of the pairwise sequence alignment problem is considered, where a score vector function takes into account simultaneously two components, similarity score and indels or gaps. Similarity score for amino acids and nucleotide sequences is obtained by a substitution matrix, such as BLOSUM or PAM, and by the subtraction of the number of matches and mismatches, respectively. This formulation is of interest to the practitioner since it allows to get rid of parameters in the usual single weighted-sum objective function and to explore a tractable set of alignments that are not reachable by any other methods. In this work, explicit recurrence equations for the dynamic programming algorithms are given as well as a new pruning technique that improves the run-time. Furthermore, the algorithm is applied to 7 PAP genes of Candida clade and the results are compared with those of a distance tree, found by simulating the divergence of these sequences from a common ancestor. Similar conclusions were achieved by the two methods. Extensions for multiple sequence alignment are also discussed.

Keywords

Multicriteria optimization, computational biology

Subject

Multicriteria optimization, computational biology

Related Project

MOSAL - Multiobjective Sequence Alignment

Conference

Bioinformatics Open Days, 40, August 2012