Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Microbial Phylogeny01:28

Microbial 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,...
Phylogenetic Trees03:21

Phylogenetic 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...
Phylogenetic Trees03:21

Phylogenetic 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...
Evolutionary Relationships through Genome Comparisons02:54

Evolutionary 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...
Phylogeny01:23

Phylogeny

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...
The Tree of Life - Bacteria, Archaea, Eukaryotes02:40

The Tree of Life - Bacteria, Archaea, Eukaryotes

The “tree of life” describes the evolution of life and the evolutionary relationships between organisms. The root of the tree is the common ancestor to all life on Earth. All other species radiate from this point, much like the branches of a tree. The numerous tips of these branches on the tree of life represent every living, or extant, species. Extinct species, which are species that no longer exist, can be found towards the center of the tree. Currently, these organisms, both extant and...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

The haplotype-resolved T2T genome for Bauhinia × blakeana sheds light on the genetic basis of flower heterosis.

GigaScience·2025
Same author

UniVar: A variant interpretation platform enhancing rare disease diagnosis through robust filtering and unified analysis of SNV, INDEL, CNV and SV.

Computers in biology and medicine·2024
Same author

SurVIndel2: improving copy number variant calling from next-generation sequencing using hidden split reads.

Nature communications·2024
Same author

Constructing telomere-to-telomere diploid genome by polishing haploid nanopore-based assembly.

Nature methods·2024
Same author

PlantCFG: A comprehensive database with web tools for analyzing candidate flowering genes in multiple plants.

Plant communications·2023
Same author

Integrated 3D genome, epigenome and transcriptome analyses reveal transcriptional coordination of circadian rhythm in rice.

Nucleic acids research·2023
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

Related Experiment Video

Updated: Jun 9, 2026

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

Computing a smallest multilabeled phylogenetic tree from rooted triplets.

Sylvain Guillemot1, Jesper Jansson, Wing-Kin Sung

  • 1Institut Gaspard Monge-Université Paris-Est, 5 boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée, France. Sylvain.Guillemot@univ-mlv.fr

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|August 25, 2010
PubMed
Summary
This summary is machine-generated.

Inferring smallest phylogenetic trees (MUL trees) is NP-hard, even with one leaf duplication. The problem is also hard to approximate, though an algorithm offers a near-optimal solution.

More Related Videos

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
10:23

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles

Published on: July 11, 2025

Related Experiment Videos

Last Updated: Jun 9, 2026

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
10:23

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles

Published on: July 11, 2025

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Algorithm Analysis

Background:

  • Phylogenetic trees model evolutionary relationships.
  • Inferring these trees from data is crucial but computationally challenging.
  • Multilabeled phylogenetic trees (MUL trees) offer a more flexible model.

Purpose of the Study:

  • To investigate the computational complexity of inferring smallest MUL trees.
  • To determine the approximability of this NP-hard problem.
  • To develop an exact algorithm for MUL tree inference.

Main Methods:

  • Proving NP-hardness for a restricted version of MUL tree inference.
  • Deriving inapproximability bounds for the minimization problem.
  • Designing a polynomial-time approximation algorithm.
  • Developing an exact exponential-time algorithm.

Main Results:

  • The problem of inferring a smallest MUL tree consistent with rooted triplets is NP-hard.
  • Even with a single leaf duplication, the problem remains NP-hard.
  • The general minimization problem is difficult to approximate.
  • An approximation algorithm achieves a ratio close to the theoretical bound.
  • An exact algorithm with exponential time and space complexity was developed.

Conclusions:

  • Inferring smallest MUL trees is computationally intractable.
  • Approximation algorithms are necessary for practical applications.
  • New inapproximability results were established for related graph partitioning problems.