Related Experiment Video
Updated: May 21, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
[A fast algorithm to build a supertree with a set of gene trees]
Molekuliarnaia Biologiia
|May 31, 2012
Summary
This study presents an efficient algorithm for constructing supertrees (species trees) from multiple input trees, addressing the computational challenges of large biological datasets. The new method ensures biological plausibility by avoiding incompatible clades, offering a practical solution for phylogenetic analysis.
Area of Science:
- Phylogenetics and computational biology
- Algorithm design and analysis
- Bioinformatics tool development
Context:
- Constructing a supertree (species tree) from multiple input trees is a fundamental problem in phylogenetics.
- The traditional supertree problem is NP-hard, limiting its applicability to large biological datasets due to high computational complexity.
- Existing methods often struggle with scalability and may not guarantee biologically plausible outputs.
Purpose:
- To reformulate the supertree construction problem for computational efficiency.
- To introduce a biologically relevant constraint: the supertree must not contain clades incompatible with the input trees.
- To develop an algorithm with low complexity suitable for large-scale phylogenetic analysis.
Summary:
- The proposed algorithm reformulates the supertree problem by requiring the absence of incompatible clades, enabling computationally effective solutions.
- The algorithm demonstrates near-quadratic complexity, even when accounting for horizontal gene transfers (HGTs).
- Without assuming HGTs, the algorithm has a proven time complexity of O(n³ * |V₀|³), where n is the number of input trees and |V₀| is the total number of species.
Impact:
- Provides a computationally efficient and biologically plausible method for supertree construction.
- Facilitates the analysis of large and complex phylogenetic datasets.
- The developed inferring program is freely available, promoting wider adoption and further research in phylogenetics.
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,...