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

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...
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...
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,...
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...
Phylogenetic Species Concept in Microbiology01:22

Phylogenetic Species Concept in Microbiology

The phylogenetic species concept (PSC) is a framework used to delineate species based on evolutionary relationships, emphasizing shared ancestry and diagnosable genetic traits. Unlike morphological or biological species concepts, the PSC is particularly advantageous for microbial taxonomy, where traditional reproductive or phenotypic criteria often fall short due to the prevalence of asexual reproduction, minimal morphological differentiation, and widespread horizontal gene transfer among...

You might also read

Related Articles

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

Sort by
Same author

The novel HLA-DRB1*08:127 allele, identified in a deceased organ donor of Scandinavian descent.

HLA·2024
Same author

DTL-RnB: Algorithms and Tools for Summarizing the Space of DTL Reconciliations.

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

Intravenous leiomyomatosis with cardiac involvement in a pregnant woman.

American journal of obstetrics and gynecology·1998
Same author

Microalbuminuria: prognostic and therapeutic implications in diabetic and hypertensive pregnancy.

Diabetic medicine : a journal of the British Diabetic Association·1995
Same author

[Prenatal alloimmune thrombocytopenia].

Harefuah·1995
Same author

[Microalbuminuria in clinical practice].

Harefuah·1995
Same journal

Mosquito Species and Gender Identification System Based on Artificial Intelligence and Image Processing Methods.

Journal of computational biology : a journal of computational molecular cell biology·2026
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
See all related articles

Related Experiment Video

Updated: Jun 10, 2026

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
08:57

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin

Published on: August 14, 2018

The co phylogeny reconstruction problem is NP-complete.

Y Ovadia1, D Fielder, C Conow

  • 1Department of Computer Science, Harvey Mudd College, Claremont, California 91711, USA.

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

The co-phylogeny reconstruction problem, crucial for understanding evolutionary relationships, is proven NP-complete. This suggests focusing on efficient approximation algorithms rather than guaranteed optimal solutions for this complex biological data challenge.

More Related Videos

A Practical Guide to Phylogenetics for Nonexperts
12:00

A Practical Guide to Phylogenetics for Nonexperts

Published on: February 5, 2014

Amplification of Near Full-length HIV-1 Proviruses for Next-Generation Sequencing
10:18

Amplification of Near Full-length HIV-1 Proviruses for Next-Generation Sequencing

Published on: October 16, 2018

Related Experiment Videos

Last Updated: Jun 10, 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

Amplification of Near Full-length HIV-1 Proviruses for Next-Generation Sequencing
10:18

Amplification of Near Full-length HIV-1 Proviruses for Next-Generation Sequencing

Published on: October 16, 2018

Area of Science:

  • Computational Biology
  • Evolutionary Biology
  • Systematic Biology

Background:

  • Co-phylogeny reconstruction explains differences in historical associations.
  • This problem is relevant in parasitology, molecular systematics, and biogeography.
  • Current software tools are often slow or provide non-optimal solutions.

Purpose of the Study:

  • To determine the computational complexity of the co-phylogeny reconstruction problem.
  • To guide future algorithm development for co-phylogeny analysis.

Main Methods:

  • Theoretical computer science analysis.
  • Proof of NP-completeness for the co-phylogeny reconstruction problem.

Main Results:

  • The co-phylogeny reconstruction problem is formally proven to be NP-complete.
  • This finding implies that finding optimal solutions in polynomial time is unlikely.

Conclusions:

  • Future research should prioritize developing efficient approximation algorithms and heuristics.
  • Focusing on optimal solutions for co-phylogeny reconstruction is computationally intractable.
  • This work impacts the development of tools for biological data analysis.