Related Experiment Video
Updated: May 22, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree
Tanja Stadler1, James H Degnan
1Institute of Integrative Biology, Universitätsstrasse 16, 8092, Zürich, Switzerland. tanja.stadler@env.ethz.ch.
Algorithms for Molecular Biology : AMB
|May 2, 2012
Summary
This study introduces a new polynomial-time algorithm for calculating gene tree probabilities, addressing computational challenges in evolutionary biology. This method aids in more accurately reconstructing ancestral species relationships from gene data.
Area of Science:
- Evolutionary biology
- Computational phylogenetics
Background:
- Gene trees can differ from species trees due to incomplete lineage sorting.
- Current methods for calculating gene tree probabilities are computationally intensive, requiring exponential time.
Purpose of the Study:
- To develop a more efficient algorithm for calculating gene tree probabilities.
- To address the computational complexity of inferring species trees from gene trees.
Main Methods:
- Developed a polynomial-time algorithm to compute the probability of a ranked gene tree topology for a given species tree.
- Ranked tree topology involves ordered internal vertices.
Main Results:
- The new algorithm calculates the probability of ranked gene tree topologies in polynomial time.
- The computational complexity for gene tree topologies with an exponential number of rankings remains an open question.
Conclusions:
- Polynomial-time algorithms for ranked gene tree probabilities can advance species tree inference.
- This may lead to more accurate reconstructions of ancestral species relationships.
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...
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.
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.
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...
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,...