A fast algorithm for determining the best combination of local alignments to a query sequence.

@article{citeulike:392446, abstract = {BACKGROUND: Existing sequence alignment algorithms assume that similarities between DNA or amino acid sequences are linearly ordered. That is, stretches of similar nucleotides or amino acids are in the same order in both sequences. Recombination perturbs this order. An algorithm that can reconstruct sequence similarity despite rearrangement would be helpful for reconstructing the evolutionary history of recombined sequences. RESULTS: We propose a graph-based algorithm for combining multiple local alignments to a query sequence into the single combination of alignments that either covers the maximal portion of the query or results in the single highest alignment score to the query. This algorithm can help study the process of genome rearrangement, improve functional gene annotation, and reconstruct the evolutionary history of recombined proteins. The algorithm takes O(n2) time, where n is the number of local alignments considered. CONCLUSIONS: We discuss two example applications of the algorithm. The algorithm is able to provide useful reconstructions of the metazoan mitochondrial genome. It is also able to increase the percentage of a query sequence's amino acid residues for which similar stretches of amino acids can be found in sequence databases.}, address = {Department of Biology, The University of New Mexico, Albuquerque, NM, USA. gconant@unm.edu}, author = {Conant, G. C. and Wagner, A. }, citeulike-article-id = {392446}, doi = {http://dx.doi.org/10.1186/1471-2105-5-62}, issn = {1471-2105}, journal = {BMC Bioinformatics}, keywords = {local\_score}, month = {May}, posted-at = {2005-11-14 16:40:52}, priority = {1}, title = {A fast algorithm for determining the best combination of local alignments to a query sequence.}, url = {http://dx.doi.org/10.1186/1471-2105-5-62}, volume = {5}, year = {2004} }

TY - JOUR ID - citeulike:392446 L3 - citeulike-article-id:392446 TI - A fast algorithm for determining the best combination of local alignments to a query sequence. JF - BMC Bioinformatics VL - 5 AD - Department of Biology, The University of New Mexico, Albuquerque, NM, USA. gconant@unm.edu SN - 1471-2105 N2 - BACKGROUND: Existing sequence alignment algorithms assume that similarities between DNA or amino acid sequences are linearly ordered. That is, stretches of similar nucleotides or amino acids are in the same order in both sequences. Recombination perturbs this order. An algorithm that can reconstruct sequence similarity despite rearrangement would be helpful for reconstructing the evolutionary history of recombined sequences. RESULTS: We propose a graph-based algorithm for combining multiple local alignments to a query sequence into the single combination of alignments that either covers the maximal portion of the query or results in the single highest alignment score to the query. This algorithm can help study the process of genome rearrangement, improve functional gene annotation, and reconstruct the evolutionary history of recombined proteins. The algorithm takes O(n2) time, where n is the number of local alignments considered. CONCLUSIONS: We discuss two example applications of the algorithm. The algorithm is able to provide useful reconstructions of the metazoan mitochondrial genome. It is also able to increase the percentage of a query sequence's amino acid residues for which similar stretches of amino acids can be found in sequence databases. KW - local_score AU - Conant, GC AU - Wagner, A PY - 2004/05/18/ UR - http://dx.doi.org/10.1186/1471-2105-5-62 ER -