Motivation: We explore the problem of constructing near-perfect phylogenies on bi-allelic haplotypes, where the deviation from perfect phylogeny is entirely due to homoplasy events. We present polynomial-time algorithms for restricted versions of the problem. We show that these algorithms can be extended to genotype data, in which case the problem is called the near-perfect phylogeny haplotyping (NPPH) problem. We present a near-optimal algorithm for the H1-NPPH problem, which is to determine if a given set of genotypes admit a phylogeny with a single homoplasy event. The time-complexity of our algorithm for the H1-NPPH problem is O(m2(n + m)), where n is the number of genotypes and m is the number of SNP sites. This is a significant improvement over the earlier O(n4) algorithm. We also introduce generalized versions of the problem. The H(1, q)-NPPH problem is to determine if a given set of genotypes admit a phylogeny with q homoplasy events, so that all the homoplasy events occur in a single site. We present an O(m(q+1)(n + m)) algorithm for the H(1,q)-NPPH problem.
Results: We present results on simulated data, which demonstrate that the accuracy of our algorithm for the H1-NPPH problem is comparable to that of the existing methods, while being orders of magnitude faster.
Availability: The implementation of our algorithm for the H1-NPPH problem is available upon request.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1093/bioinformatics/btl262 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Transcriptome sequencing data provide a solid base to understand the phylogenetic relationships, biogeography and reticulated evolution of the genus Zamia L. (Cycadales: Zamiaceae).
Ann Bot
November 2024
Key Laboratory of Southern Subtropical Plant Diversity, Fairy Lake Botanical Garden Shenzhen & Chinese Academy of Sciences, Shenzhen, 518004, China.
Background And Aims: Cycads are a key lineage to understand the early evolution of seed plants and their response to past environmental changes. However, tracing the evolutionary trajectory of cycad species is challenging when the robust relationships at inter- or infrageneric level are not well resolved.
Methods: Here, using 2901 single-copy nuclear genes, we explored the species relationships and gene flow within the second largest genus of cycads, i.
Bayesian tip-dated phylogeny and biogeography of Cissampelideae (Menispermaceae): Mitigating the effects of homoplastic morphological characters.
Cladistics
August 2024
State Key Laboratory of Plant Diversity and Prominent Crops, Institute of Botany, Chinese Academy of Sciences, Beijing, 100093, China.
Article Synopsis
- Understanding the integration of morphological and molecular data is crucial for accurately placing fossil taxa and studying evolutionary processes.
- The study demonstrates that solely using morphological data can lead to incorrect classifications of fossil taxa, while combining morphological data with molecular information significantly improves their placement.
- Results indicate that Cissampelideae fossils were better resolved after removing misleading morphological traits, revealing insights into their historical diversification and dispersal patterns across continents.
A major question in evolutionary biology is how often the same developmental events, mechanisms and genes are reused in the recurrent evolution of similar phenotypes. If this happens frequently, it would suggest that evolution is often constrained by developmental genetic mechanisms. To help address this question, we used adherens junction staining and laser ablation to analyze the development underlying several features of nematode male tails have evolved recurrently.
View Article and Find Full Text PDFUnmasking microsatellite deceptiveness and debunking hybridization with SNPs in four marine copepod species of Calanus.
Mol Ecol
December 2023
Faculty of Biosciences and Aquaculture, Nord University, Bodø, Norway.
Interspecific hybridization events are on the rise in natural systems due to climate change disrupting species barriers. Across taxa, microsatellites have long been the molecular markers of choice to identify admixed individuals. However, with the advent of high-throughput sequencing easing the generation of genome-wide datasets, incorrect reports of hybridization resulting from microsatellite technical artefacts have been uncovered in a growing number of taxa.
View Article and Find Full Text PDFRANBP2 evolution and human disease.
FEBS Lett
October 2023
Institut de Recherche en Infectiologie de Montpellier (IRIM), University of Montpellier, France.
Article Synopsis
- RANBP2/Nup358 is a crucial component of the nuclear pore complex, playing key roles in processes like SUMOylation and nucleocytoplasmic transport.
- Dysregulation or mutations of RANBP2 are linked to serious health issues, including various diseases such as cancer and neurodegenerative disorders, as well as its involvement in viral infections.
- The evolution of the RANBP2 gene has resulted in a family of related genes with still largely unknown functions, indicating potential advantages for organisms but also highlighting gaps in research.
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!