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

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

Evolutionary Relationships through Genome Comparisons

7.1K
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...
7.1K

You might also read

Related Articles

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

Sort by
Same author

Scalable computation of ultrabubbles in pangenomes by orienting bidirected graphs.

Bioinformatics (Oxford, England)·2026
Same author

Real-time Targeted Enrichment in Single-cell Long-read Sequencing.

Genomics, proteomics & bioinformatics·2026
Same author

EMERALD-UI: an interactive web application to unveil novel protein biology hidden in the alternative alignment space.

Bioinformatics (Oxford, England)·2026
Same author

Minimum flow decomposition in graphs with cycles using integer linear programming.

Journal of global optimization : an international journal dealing with theoretical and computational aspects of seeking global optima and their applications in science, management and engineering·2025
Same author

A single-cell, long-read, isoform-resolved case-control study of FTD reveals cell-type-specific and broad splicing dysregulation in human brain.

Cell reports·2025
Same author

A spatial long-read approach at near-single-cell resolution reveals developmental regulation of splicing and polyadenylation sites in distinct cortical layers and cell types.

Nature communications·2025

Related Experiment Video

Updated: Mar 8, 2026

High-Throughput Dissociation and Orthotopic Implantation of Breast Cancer Patient-Derived Xenografts
06:06

High-Throughput Dissociation and Orthotopic Implantation of Breast Cancer Patient-Derived Xenografts

Published on: December 20, 2024

1.4K

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.

Ademir Hujdurovic, Ursa Kacar, Martin Milanic

    IEEE/ACM Transactions on Computational Biology and Bioinformatics
    |January 24, 2017
    PubMed
    Summary
    This summary is machine-generated.

    This study disproves claims about deconvoluting mixed tumor samples and proves the problem is NP-hard. It also introduces efficient algorithms for analyzing tumor evolution and cancer mutations.

    More Related Videos

    Simple and Rapid Method to Obtain High-quality Tumor DNA from Clinical-pathological Specimens Using Touch Imprint Cytology
    11:20

    Simple and Rapid Method to Obtain High-quality Tumor DNA from Clinical-pathological Specimens Using Touch Imprint Cytology

    Published on: March 21, 2018

    11.5K
    Automated Dissection Protocol for Tumor Enrichment in Low Tumor Content Tissues
    06:44

    Automated Dissection Protocol for Tumor Enrichment in Low Tumor Content Tissues

    Published on: March 29, 2021

    3.0K

    Related Experiment Videos

    Last Updated: Mar 8, 2026

    High-Throughput Dissociation and Orthotopic Implantation of Breast Cancer Patient-Derived Xenografts
    06:06

    High-Throughput Dissociation and Orthotopic Implantation of Breast Cancer Patient-Derived Xenografts

    Published on: December 20, 2024

    1.4K
    Simple and Rapid Method to Obtain High-quality Tumor DNA from Clinical-pathological Specimens Using Touch Imprint Cytology
    11:20

    Simple and Rapid Method to Obtain High-quality Tumor DNA from Clinical-pathological Specimens Using Touch Imprint Cytology

    Published on: March 21, 2018

    11.5K
    Automated Dissection Protocol for Tumor Enrichment in Low Tumor Content Tissues
    06:44

    Automated Dissection Protocol for Tumor Enrichment in Low Tumor Content Tissues

    Published on: March 29, 2021

    3.0K

    Area of Science:

    • Computational Biology
    • Bioinformatics
    • Cancer Genomics

    Background:

    • Deconvoluting mixed tumor samples is crucial for understanding tumor evolution and identifying cancer mutations.
    • Previous models, like Hajirasouliha and Raphael's (WABI 2014), aimed to reconstruct perfect phylogenies from sequencing data.
    • Key challenges include the computational complexity of matrix decomposition and phylogenetic inference.

    Purpose of the Study:

    • To re-evaluate and disprove existing claims regarding the computational complexity of the mixed perfect phylogeny problem.
    • To provide a correct proof of the NP-hardness for this deconvolution task.
    • To develop novel algorithms for efficient and optimal solutions to tumor sample analysis.

    Main Methods:

    • Disproving previously published NP-hardness proofs for the mixed perfect phylogeny problem.
    • Developing a new, independent proof to establish the problem's NP-hardness.
    • Proving NP-completeness for a related variant of the problem.
    • Designing a heuristic algorithm utilizing co-comparability graph coloring.
    • Implementing a polynomial-time algorithm for specific matrix instances.

    Main Results:

    • Several claims regarding the mixed perfect phylogeny problem, including its NP-hardness, were disproven.
    • The study successfully established the problem as NP-hard through a novel proof.
    • A variant of the problem was proven to be NP-complete.
    • An efficient heuristic and a polynomial-time algorithm were developed and implemented.

    Conclusions:

    • The computational complexity landscape of deconvoluting mixed tumor samples has been clarified.
    • New algorithmic approaches offer practical solutions for analyzing tumor evolution and cancer mutations from sequencing data.
    • Open-source implementations are available for broader research application.