Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
Comparative Study
. 1995 Fall;2(3):459-72.
doi: 10.1089/cmb.1995.2.459.

Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment

S K Gupta  1 , J D Kececioglu, A A Schäffer
Affiliations
Comparative Study

Improving the practical space and time efficiency of the shortest-paths approach to sum-of-pairs multiple sequence alignment

S K Gupta et al. J Comput Biol. 1995 Fall.

Abstract

The MSA program, written and distributed in 1989, is one of the few existing programs that attempts to find optimal alignments of multiple protein or DNA sequences. The MSA program implements a branch-and-bound technique together with a variant of Dijkstra's shortest paths algorithm to prune the basic dynamic programming graph. We have made substantial improvements in the time and space usage of MSA. The improvements make feasible a variety of problem instances that were not feasible previously. On some runs we achieve an order of magnitude reduction in space usage and a significant multiplicative factor speedup in running time. To explain how these improvements work, we give a much more detailed description of MSA than has been previously available. In practice, MSA rarely produces a provably optimal alignment and we explain why.

PubMed Disclaimer

Similar articles

See all similar articles

Cited by

See all "Cited by" articles

Publication types

LinkOut - more resources