On multi-objective sequence alignment: formulation and algorithms

Description:  Sequence alignment is used to identify regions of similarity that may indicate functional, structural and/or evolutionary relationships between two or more biological sequences. Usually, the quality of an alignment is given by a score function that is a weighted sum of several components, such as the number of matches, mismatches, indels and/or gaps in the alignment. However, it is not clear how to set up the weights in advance. Moreover, several choices for the weights may give rise to different alignments. In this thesis, the multi-objective formulation of the sequence alignment problem is considered, which provides the best set of alignments that can be achieved by optimizing the several components simultaneously. This set of alignments is a superset of those obtained by a weighted sum approach. In addition, this formulation does not need weights. The goal of this thesis is twofold: (i) to design and analyse exact and approximate algorithms for several variants of this problem; (ii) to develop procedures that allow to extract an interesting subset of alignments from the optimal trade-off. An in-depth experimental analysis with both random and real-life data on pairwise and multiple sequence alignment will be considered. Date:  2012-12-19 Start Time:   14:30 Speaker:  Maryam Abbasi (DEI, Univ. Coimbra) Institution:  Department of Informatics Engineering, University of Coimbra Research Groups: -Numerical Analysis and Optimization See more:   <Main>