Sequence Alignment Based on segment to segment Comparision

Abstract

"Computational Biology. MSA is a known NP-Complete Problem and hence the focus is always on approximation algorithms and heuristics. Most of the current MSA methods work at residue level i.e they are based on residue to residue comparisions. (A residue corresponds to a single character of a sequence).But recent advances in biology have made available structural and functional information using which a sequence can be decomposed into segments where a segment is acontinuous stretch of residues.In this thesis, we study MSA based on segment to segment comparision. The two main advantages of segment to segment comparision are, we can reduce the search space and we can incorporate structural as well as functional information in MSA thus improving the quality of MSA. We first study the complexity of the problem and then show how it relates to MSA based on residue to residue comparisions.We also look at the problem from a graph theoretical point of view. Finally, we propose various heuristics to solve large instances of the problem quickly. The heuristics which we discuss are based on divide-and- conquer, progressive and iterative approaches."