Related Experiment Video
Updated: Jul 15, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
Reconstruction of ancestral genomic sequences using likelihood
1Department of Numerical Analysis and Computer Science, KTH, Stockholm, Sweden. isaac@nada.kth.se
Summary
Reconstructing ancestral genomes is crucial in computational biology. This study introduces novel algorithms offering guaranteed approximations and optimal solutions for ancestral sequence reconstruction, even when phylogenetic trees are unknown.
Area of Science:
- Computational Biology
- Bioinformatics
- Genomics
Background:
- Reconstructing ancestral genomic sequences is vital for understanding evolutionary history.
- Current heuristic methods lack performance guarantees, necessitating improved algorithms.
Purpose of the Study:
- To develop algorithms for ancestral genome reconstruction with performance guarantees.
- To address both scenarios: known and unknown phylogenetic trees.
Main Methods:
- Developed approximation algorithms with a log-likelihood ratio guarantee.
- Implemented a fixed-parameter tractable (FPT) algorithm for optimal solutions on small trees.
- Created a Polynomial Time Approximation Scheme (PTAS) by combining approximation and FPT algorithms.
Main Results:
- The approximation algorithm provides a solution with a log-likelihood ratio of 2.
- The FPT algorithm is efficient for small numbers of taxa.
- The PTAS offers arbitrarily good approximation guarantees.
- Algorithms were validated on synthetic and biological data, including hominid mitochondrial genomes and lentiviruses.
Conclusions:
- The developed algorithms significantly advance ancestral genome reconstruction capabilities.
- These methods provide reliable solutions for both theoretical and practical biological questions.
- The study offers a valuable toolkit for evolutionary and genomic research.
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:37Gene Duplication and Divergence
The seminal work of Ohno in 1970 popularized the idea of gene duplication and divergence. DNA sequence comparison studies reveal that a large portion of the genes in bacteria, archaebacteria, and eukaryotes was generated by gene duplication and divergence, indicating its critical role in evolution.
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are characterized.
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are characterized.
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:36Genome Annotation and Assembly
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
03:00Next-generation Sequencing
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.