Related Experiment Video
Updated: Aug 31, 2025
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
35.4K
Treewidth-based algorithms for the small parsimony problem on networks.
Celine Scornavacca1, Mathias Weller2
1ISEM, Université de Montpellier, CNRS, IRD, EPHE, Montpellier, France.
Algorithms for Molecular Biology : AMB
|August 20, 2022
Summary
This study presents new algorithms for phylogenetic networks, efficiently calculating evolutionary character states. These methods improve upon existing approaches for parsimony scores on networks with low treewidth.
Area of Science:
- Bioinformatics
- Computational Biology
- Phylogenetics
Background:
- Phylogenetic reconstruction is a key challenge in bioinformatics.
- The Small Parsimony problem is crucial for tree reconstruction but complex on networks with reticulate events.
- Existing parsimony scores on networks are NP-hard, with algorithms parameterized by character states and reticulate events.
Purpose of the Study:
- To develop efficient algorithms for the Small Parsimony problem on phylogenetic networks.
- To address three proposed versions of parsimony scores on networks.
- To leverage the treewidth parameter for algorithmic efficiency.
Main Methods:
- Dynamic programming algorithms parameterized by treewidth.
- Consideration of the treewidth of the underlying undirected graph of the network.
- Formulation of treewidth-based dynamic programming for phylogenetic networks.
Main Results:
- Algorithms for three versions of the parsimony problem on networks with running times dependent on treewidth.
- Improved and subsumed previously known algorithms for these parsimony score variants.
- A novel formulation of tree decompositions using "agreeing trees".
Conclusions:
- Enables computation of popular parsimony scores on phylogenetic networks with low treewidth.
- Enhances existing algorithms for parsimony score variants.
- Aims to make treewidth-based algorithms more accessible to researchers in phylogenetic networks.
Keywords:
Dynamic programmingParameterized complexityParsimonyPhylogenetic networksPhylogeneticsTreewidthMore Related Videos
09:49Divergence of Root Microbiota in Different Habitats based on Weighted Correlation Networks
Published on: September 25, 2021
4.4K
10:44Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
Published on: December 7, 2021
2.3K
Related Concept Videos
03:21Phylogenetic Trees
46.0K
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.
46.0K
01:19Survival Tree
142
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
142
02:26Protein Networks
4.1K
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
4.1K
02:54Evolutionary Relationships through Genome Comparisons
6.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...
6.1K
01:20Applications of Molecular Taxonomy
83
Molecular taxonomy has revolutionized the understanding and classification of bacteria, providing precise insights into their diversity, evolutionary relationships, and ecological roles. By utilizing molecular techniques such as DNA sequencing and fingerprinting, researchers have made significant strides in various fields related to bacterial studies.Resolving Taxonomic AmbiguitiesMolecular taxonomy has been instrumental in distinguishing closely related bacterial species initially thought to...
83
02:04Conservation of Small Populations
13.3K
Small population sizes put a species at extreme risk of extinction due to a lack of variation, and a consequent decrease in adaptability. This weakens the chances of survival under pressures such as climate change, competition from other species, or new diseases. Large populations are more likely to survive pressures such as these, as such populations are more likely to harbor individuals that have genetic variants that are adaptive under new stresses. Small populations are much less...
13.3K