Related Experiment Video
Updated: Aug 6, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
Constructing near-perfect phylogenies with multiple homoplasy events
Ravi Vijaya Satya1, Amar Mukherjee, Gabriela Alexe
1School of EECS, University of Central Florida, Orlando, FL 32816-2362, USA. rvijaya@cs.ucf.edu
Bioinformatics (Oxford, England)
|July 29, 2006
Summary
We developed faster algorithms for constructing near-perfect phylogenies from genetic data, specifically addressing homoplasy events in haplotype and genotype data. Our new methods significantly improve computational efficiency for the near-perfect phylogeny haplotyping problem.
Area of Science:
- Computational Biology
- Bioinformatics
- Phylogenetics
Background:
- Investigates the construction of near-perfect phylogenies for bi-allelic haplotypes, focusing on homoplasy as the sole source of deviation.
- Extends algorithms to genotype data, defining the near-perfect phylogeny haplotyping (NPPH) problem.
Purpose of the Study:
- To present efficient polynomial-time algorithms for constructing near-perfect phylogenies, particularly for the NPPH problem.
- To develop a near-optimal algorithm for the H1-NPPH problem (single homoplasy event) with improved time complexity.
- To generalize the problem to H(1, q)-NPPH (q homoplasy events at a single site) and provide an efficient algorithm.
Main Methods:
- Developed a novel algorithm for the H1-NPPH problem with a time complexity of O(m^2(n + m)), where n is the number of genotypes and m is the number of SNP sites.
- Extended this approach to solve the generalized H(1, q)-NPPH problem with an algorithm complexity of O(m(q+1)(n + m)).
- Algorithms are designed for polynomial time, offering significant speed improvements over existing O(n^4) methods.
Main Results:
- The algorithm for H1-NPPH achieves a time complexity of O(m^2(n + m)), a substantial improvement over previous O(n^4) algorithms.
- Simulated data results show comparable accuracy to existing methods for H1-NPPH, but with drastically reduced computation time.
- An efficient algorithm for the H(1, q)-NPPH problem is presented with O(m(q+1)(n + m)) complexity.
Conclusions:
- The developed algorithms provide a computationally efficient solution for constructing near-perfect phylogenies from genotype data, especially in the presence of homoplasy.
- The new methods offer a significant speed-up for the H1-NPPH and generalized H(1, q)-NPPH problems, making them practical for larger datasets.
- Implementation of the H1-NPPH algorithm is available upon request.
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: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,...
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:23Phylogeny
Phylogeny is concerned with the evolutionary diversification of organisms or groups of organisms. A group of organisms with a name is called a taxon (singular). Taxa (plural) can span different levels of the evolutionary hierarchy. For instance, the group containing all birds is a taxon (comprising the class Aves), and the group of all species of daisies (the genus Bellis) is a taxon. Phylogenies can likewise include just one genus (i.e., depict species relationships) or span an entire...
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...