Related Experiment Video
Updated: Jul 10, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice
Srinath Sridhar1, Kedar Dhamdhere, Guy Blelloch
1Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. srinath@cs.cmu.edu
IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 3, 2007
Summary
We developed new algorithms for reconstructing near-perfect phylogenetic trees (BNPP) from binary data. These methods are computationally efficient and robust to real-world evolutionary imperfections.
Area of Science:
- Computational Biology
- Phylogenetics
- Evolutionary Biology
Background:
- Perfect phylogeny assumes single mutations per character, limiting real-world applicability.
- Real biological data often contains multiple mutations, requiring more robust models.
- Existing methods struggle with data imperfections, impacting phylogenetic accuracy.
Purpose of the Study:
- To develop algorithms for reconstructing near-perfect phylogenetic trees (BNPP).
- To address limitations of perfect phylogeny models with real biological data.
- To provide computationally feasible and accurate phylogenetic reconstruction methods.
Main Methods:
- Developed two algorithms for optimal near-perfect phylogeny reconstruction.
- Analyzed algorithms for fixed-parameter tractability based on mutation counts.
- Implemented and empirically evaluated algorithm performance on biological datasets.
Main Results:
- Demonstrated fixed-parameter tractability for BNPP under specific conditions.
- Showcased practical efficiency of implemented algorithms on significant datasets.
- Provided the first practical algorithms for guaranteed optimal near-perfect phylogenies.
Conclusions:
- The BNPP problem is proven to be fixed-parameter tractable.
- The developed algorithms offer practical, efficient, and accurate phylogenetic reconstruction.
- These methods are suitable for large and complex biological datasets.
Related Concept Videos
01:28Microbial Phylogeny
Understanding the evolutionary relationships among microorganisms is fundamental to microbial ecology and taxonomy. Phylogenetic trees are essential tools for inferring these relationships, relying primarily on comparative analyses of molecular sequences such as DNA, RNA, or proteins. In microbial studies, these trees typically depict the evolutionary paths of diverse bacterial and archaeal species by mapping genetic differences accumulated over time.Phylogenetic trees are composed of tips,...
03:21Phylogenetic Trees
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.The length of the branches can depict time or the relative amount of change among organisms. For instance, the branch length might indicate the number of amino acid changes in the sequence that underlies the...
03:21Phylogenetic Trees
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.The length of the branches can depict time or the relative amount of change among organisms. For instance, the branch length might indicate the number of amino acid changes in the sequence that underlies the...
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...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...