Related Experiment Video
Updated: Jul 15, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
Lower bounds on multiple sequence alignment using exact 3-way alignment.
Charles J Colbourn1, Sudhir Kumar
1Center for Evolutionary Functional Genomics, The Biodesign Institute, Arizona State University, Tempe, AZ 85287-5301, USA. Charles.Colbourn@asu.edu
BMC Bioinformatics
|May 2, 2007
Summary
Improving lower bounds for multiple sequence alignment quality is crucial. New methods using 3-way alignments offer better accuracy and reduced computation time for sum-of-pairs (SP) cost estimation.
Area of Science:
- Bioinformatics
- Computational Biology
- Algorithm Analysis
Background:
- Multiple sequence alignment (MSA) is essential in bioinformatics.
- Optimal MSA computation time grows exponentially with sequence number, necessitating heuristic approaches.
- Assessing alignment quality requires reliable lower bounds, especially when optimal alignments are infeasible.
Purpose of the Study:
- To develop and evaluate novel methods for computing lower bounds on sum-of-pairs (SP) alignment cost.
- To improve the accuracy and efficiency of alignment quality assessment.
Main Methods:
- Considered two standard and two new methods utilizing exact 2-way and 3-way alignments.
- Employed exhaustive computation of exact 3-way alignments.
- Developed an efficient heuristic for computing a subset of exact 3-way alignments.
Main Results:
- A new method using exhaustive 3-way alignments improved lower bounds on SP cost.
- An efficient heuristic for selecting a subset of 3-way alignments achieved comparable accuracy with significantly less computation.
- The heuristic random packing method demonstrated substantial computational savings.
Conclusions:
- Calculating lower bounds on SP cost can be enhanced by integrating 3-way and 2-way alignment information.
- A judicious selection of 3-way alignments offers improved lower bounds with minimal additional computational effort.
Related Concept Videos
02:54Evolutionary Relationships through Genome Comparisons
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
01:49Conserved Binding Sites
Many proteins’ biological role depends on their interactions with their ligands, small molecules that bind to specific locations on the protein known as ligand-binding sites. Ligand-binding sites are often conserved among homologous proteins as these sites are critical for protein function.
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
02:07Improving Translational Accuracy
Base complementarity between the three base pairs of mRNA codon and the tRNA anticodon is not a failsafe mechanism. Inaccuracies can range from a single mismatch to no correct base pairing at all. The free energy difference between the correct and nearly correct base pairs can be as small as 3 kcal/ mol. With complementarity being the only proofreading step, the estimated error frequency would be one wrong amino acid in every 100 amino acids incorporated. However, error frequencies observed in...