University of Vermont
Computer Science Technical Report CS-05-9
Space-efficient Algorithms for the Constrained Multiple Sequence
Alignment Problem
by
Dan He and Abdullah N. Arslan
Abstract
It is well known that A* algorithm reduces the search space in
many applications. For shortest path computations, the algorithm
uses a heuristic estimator which can better guide the search to
the destination. It allocates memory dynamically to store only the
necessary vertices, which are those vertices in its open list and
close list. Therefore, an A* algorithm for the shortest paths
search problem is much more space efficient than ordinary search
algorithm such as the dynamic programming algorithm and the
Dijkstra algorithm. The constrained multiple sequence
alignment problem (CMSA) aims to align similar subsequences in
the same region under the guidance of a given pattern
(constraint). The CMSA problem can be considered as an optimal
path search problem in the dynamic programming matrix. In this
paper, we propose two A*-based algorithms which we
experimentally show that in practice they solve the CMSA problem
using much less memory than does the ordinary dynamic programming
algorithm.
Last updated: Sep 10,
2005.