Related Experiment Video
Updated: Jul 18, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences.
1Digital Medicine Initiative, Kyushu University, Fukuoka 812-8582, Japan. katoh@bioreg.kyushu-u.ac.jp
Bioinformatics (Oxford, England)
|November 23, 2006
Summary
A new approximate algorithm, PartTree, significantly speeds up multiple sequence alignment (MSA) by reducing guide tree calculation time from cubic to log-linear complexity. This enables the alignment of tens of thousands of sequences rapidly on standard hardware.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- Multiple sequence alignment (MSA) is crucial for analyzing large biological datasets.
- Calculating guide trees for MSA is computationally intensive, with complexities of O(N^2) to O(N^3), hindering scalability for large sequence sets (>10,000).
Purpose of the Study:
- To develop a faster algorithm for constructing guide trees in MSA.
- To enable efficient alignment of a large number of sequences.
Main Methods:
- Developed an approximate algorithm named PartTree.
- Implemented PartTree to achieve an average time complexity of O(N log N) for guide tree construction.
Main Results:
- The PartTree algorithm enables MSA of approximately 60,000 sequences in minutes on a desktop computer.
- Benchmark tests using Pfam showed a minimal accuracy loss of several percent due to the approximation.
Conclusions:
- PartTree offers a significant speedup for large-scale MSA.
- The algorithm is integrated into the MAFFT alignment package, making it accessible to researchers.
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.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...
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: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:21RNA-seq
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
01:29Modern Molecular Taxonomy
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...