Related Experiment Video
Updated: Jul 19, 2026
12:27
Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
Reconstructing an ultrametric galled phylogenetic network from a distance matrix
Ho-Leung Chan1, Jesper Jansson, Tak-Wah Lam
1Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong, PR China. hlchan@cs.hku.hk
Journal of Bioinformatics and Computational Biology
|September 29, 2006
Summary
This study introduces an efficient algorithm for constructing phylogenetic networks from evolutionary distances. It also proves the computational difficulty of related problems involving incomplete or partial distance data.
Area of Science:
- Computational Biology
- Phylogenetics
- Evolutionary Biology
Background:
- Phylogenetic tree reconstruction aims to infer evolutionary relationships using distance matrices.
- Extending these methods to phylogenetic networks, which model reticulate evolution, presents new challenges.
Purpose of the Study:
- To develop an algorithm for constructing ultrametric galled networks from distance matrices.
- To investigate the computational complexity of related problems concerning phylogenetic networks.
Main Methods:
- An O(n^2 log n) time algorithm was developed for network construction.
- Proof techniques were used to establish NP-hardness for related subproblems.
Main Results:
- An efficient algorithm determines the existence and constructs an ultrametric galled network satisfying a given distance matrix.
- The algorithm guarantees the construction of a network with the minimum number of hybrid nodes.
- Finding the largest submatrix compatible with such a network and handling incomplete matrices are proven to be NP-hard.
Conclusions:
- The study provides an efficient solution for a specific phylogenetic network reconstruction problem.
- It highlights the inherent computational complexity of inferring phylogenetic networks from incomplete or partial evolutionary distance data.
Related Concept Videos
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: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...
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:29Distance Problem
When an object's velocity changes over time, the total distance traveled can be determined by summing small displacement intervals over short increments. This approach approximates the true distance through numerical summation and the use of integral calculus. An estimate of the total displacement can be obtained by measuring velocity at regular intervals and multiplying each value by the corresponding time step.If a runner accelerates over the first three seconds of a race, speed measurements...
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...