Related Experiment Videos
Optimal sum-of-pairs multiple sequence alignment using incremental Carrillo and Lipman bounds.
Arun S Konagurthu1, Peter J Stuckey
1Department of Computer Science and Software Engineering, The University of Melbourne, Victoria, 3010, Australia.
Summary
This study introduces a novel method to optimize multiple sequence alignment, significantly reducing computational search space. The enhanced approach improves upon existing techniques, making complex alignments more feasible.
Area of Science:
- Bioinformatics
- Computational Biology
- Molecular Biology
Background:
- Multiple sequence alignment (MSA) is crucial in molecular biology but computationally intensive.
- Dynamic programming algorithms for MSA face scalability issues due to large space requirements.
- Existing methods like Carrillo and Lipman's offer partial solutions by reducing search space.
Purpose of the Study:
- To generalize existing bounds for optimizing MSA.
- To present a novel approach for finding optimal sum-of-pairs (SP) alignments.
- To enable drastic pruning of the search space for computationally infeasible alignments.
Main Methods:
- Generalization of Carrillo and Lipman bounds.
- Development of an incremental pruning strategy for the alignment search space.
- Application of bounds to the sum-of-pairs scoring measure for MSA.
Main Results:
- The novel approach allows for significant pruning of the search space polytope.
- Achieved pruning is more drastic compared to the original Carrillo and Lipman method.
- Enables previously infeasible MSA runs.
Conclusions:
- The generalized bounds and incremental pruning offer a more efficient method for optimal SP-MSA.
- This advancement significantly improves the feasibility of large-scale multiple sequence alignment.
- The approach has broad implications for various scientific disciplines relying on sequence alignment.