Related Experiment Videos
A fast algorithm for determining the best combination of local alignments to a query sequence
Gavin C Conant1, Andreas Wagner
1Department of Biology, The University of New Mexico, Albuquerque, NM, USA. gconant@unm.edu
BMC Bioinformatics
|May 20, 2004
Summary
This study introduces a novel graph-based algorithm to reconstruct sequence similarity despite genomic rearrangements. The method aids in understanding genome evolution and improving gene annotation for recombined sequences.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Traditional sequence alignment assumes linear ordering of similarities, which is disrupted by recombination.
- Recombination events alter the order of sequence segments, posing challenges for evolutionary reconstruction.
- A method to identify sequence similarity despite rearrangements is needed for evolutionary studies.
Purpose of the Study:
- To develop a graph-based algorithm for combining multiple local sequence alignments.
- To create an algorithm that reconstructs sequence similarity in the presence of genomic rearrangements.
- To enhance the analysis of evolutionary histories for recombined sequences.
Main Methods:
- A graph-based algorithm is proposed to merge multiple local alignments.
- The algorithm identifies the optimal combination of alignments maximizing query coverage or alignment score.
- The computational complexity is O(n^2), where n is the number of local alignments.
Main Results:
- The algorithm effectively combines local alignments to reconstruct sequence similarity.
- It can identify maximal query coverage or the highest alignment score.
- Demonstrated utility in reconstructing metazoan mitochondrial genomes.
Conclusions:
- The developed algorithm aids in studying genome rearrangement processes.
- It improves functional gene annotation by identifying homologous regions.
- The method enhances the reconstruction of evolutionary histories for recombined proteins and genomes.