Cost Partitioning Techniques For Multiple Sequence Alignment Master thesis

Multiple Sequence Alignment (MSA) is the problem of aligning multiple biological sequences in the evolutionary most plausible way. It can be viewed as the shortest path problem through an n-dimensional lattice. Because of its large branching factor of 2^n − 1, it has found broad attention in the artificial intelligence … See more

Multiple Sequence Alignment (MSA) is the problem of aligning multiple biological sequences in the evolutionary most plausible way. It can be viewed as the shortest path problem through an n-dimensional lattice. Because of its large branching factor of 2^n − 1, it has found broad attention in the artificial intelligence community. Finding a globally optimal solution for more than a few sequences requires sophisticated heuristics and bounding techniques in order to solve the problem in an acceptable time and within memory limitations. In this thesis, we show how existing heuristics fall into the category of combining certain pattern databases. We combine arbitrary pattern collections that can be used as heuristic estimates and apply cost partitioning techniques from classical planning for MSA. We implement two of those heuristics for MSA and compare their estimates to the existing heuristics.

See less