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

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...
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...
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...
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,...
Multi-species Conserved Sequences02:51

Multi-species Conserved Sequences

Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale  studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...

You might also read

Related Articles

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

Sort by
Same author

An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding.

Algorithms for molecular biology : AMB·2016
Same author

A Resolution of the Static Formulation Question for the Problem of Computing the History Bound.

IEEE/ACM transactions on computational biology and bioinformatics·2016
Same author

Faster algorithms for RNA-folding using the Four-Russians method.

Algorithms for molecular biology : AMB·2014
Same author

Constructing perfect phylogenies and proper triangulations for three-state characters.

Algorithms for molecular biology : AMB·2012
Same author

Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem.

IEEE/ACM transactions on computational biology and bioinformatics·2011
Same author

Untangling tanglegrams: comparing trees by their drawings.

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

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

Related Experiment Video

Updated: Jun 14, 2026

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

The Multi-State Perfect Phylogeny Problem with missing and removable data: solutions via integer-programming and

Dan Gusfield1

  • 1Department of Computer Science, University of California, Davis, Davis, California 95616, USA. gusfield@cs.ucdavis.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|April 10, 2010
PubMed
Summary
This summary is machine-generated.

This study introduces new methods for the Multi-State Perfect Phylogeny Problem, addressing missing data and character removal. Novel graph theory approaches provide practical solutions for phylogenetic data analysis.

More Related Videos

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

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 14, 2026

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

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
  • Graph Theory

Background:

  • The Binary Perfect Phylogeny Problem is extended to multi-state characters.
  • Existing models have limitations when dealing with missing data or character selection.

Purpose of the Study:

  • To address the Missing Data (MD), Character-Removal (CR), and Missing-Data Character-Removal (MDCR) problems within the multi-state perfect phylogeny framework.
  • To develop and test novel computational methods for these phylogenetic problems.

Main Methods:

  • Integer Linear Programming (ILP) for specific state cases (3, 4, 5).
  • Development of a general theory for the MD problem using chordal graph theory and minimal triangulation.
  • Implementation of the general theory using ILP and empirical testing.

Main Results:

  • New necessary and sufficient conditions for the existence of multi-state perfect phylogenies with or without missing data.
  • Demonstrated practical applicability of the developed methods for complex phylogenetic datasets.
  • Identified surprising combinatorial structures in multi-state perfect phylogenies.

Conclusions:

  • The proposed methods offer efficient and practical solutions for multi-state perfect phylogeny problems, including those with missing data.
  • The general theory based on chordal graphs advances the understanding of phylogenetic data structure.
  • Empirical results confirm the scalability and effectiveness of the algorithms in real-world phylogenetics applications.