Dynamic Programming Algorithms for Biobjective Sequence Alignment



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.


Multicriteria optimization, computational biology


Multicriteria optimization, computational biology

Related Project

MOSAL - Multiobjective Sequence Alignment


Bioinformatics Open Days, 40, August 2012

Cited by

No citations found