Extensions of Some Efficient Algorithms for Similarity Searches
Nimisha Gupta and Priti Shankar
IISc-CSA-TR-2000-1
(January 2000) Available formats: [ps] [ps.gz]
Filed on June 21, 2004
Local similarity searches in biological databases and multiple sequence
alignment are important problems in computational biology. In this paper,
an algorithm called the stack algorithm, well known in the area of coding
theory, has been proposed for use in the last phase of a local alignment
algorithm like Gapped BLAST,to overcome the inefficiencies of an approach
based on dynamic programming. The $A^*$ algorithm, originally proposed for
applications in artificial intelligence, was later adapted for multiple
sequence alignment. We show that it is possible to modify this algorithm
to incorporate natural gap costs, while retaining its computational
efficiency. We also investigate the effect of using upper bounds in reducing
the search space of this algorithm. Some results from the implementation
of both these algorithms are reported.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2000/1/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]