Techniques for the verification of minimal phylogenetic trees illustrated with ten mammalian haemoglobin sequences.
Ontology highlight
ABSTRACT:
SUBMITTER: Penny D
PROVIDER: S-EPMC1162494 | biostudies-other | 1980 Apr
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Clustering homologous sequences based on their similarity is a problem that appears in many bioinformatics applications. The fact that sequences cluster is ultimately the result of their phylogenetic relationships. Despite this observation and the natural ways in which a tree can define clusters, most applications of sequence clustering do not use a phylogenetic tree and instead operate on pairwise sequence distances. Due to advances in large-scale phylogenetic inference, we argue that tree-based clustering is under-utilized. We define a family of optimization problems that, given an arbitrary tree, return the minimum number of clusters such that all clusters adhere to constraints on their heterogeneity. We study three specific constraints, limiting (1) the diameter of each cluster, (2) the sum of its branch lengths, or (3) chains of pairwise distances. These three problems can be solved in time that increases linearly with the size of the tree, and for two of the three criteria, the algorithms have been known in the theoretical computer scientist literature. We implement these algorithms in a tool called TreeCluster, which we test on three applications: OTU clustering for microbiome data, HIV transmission clustering, and divide-and-conquer multiple sequence alignment. We show that, by using tree-based distances, TreeCluster generates more internally consistent clusters than alternatives and improves the effectiveness of downstream applications. TreeCluster is available at https://github.com/niemasd/TreeCluster.
| S-EPMC6705769 | biostudies-literature
Project description:MotivationThe ability to simulate epidemics as a function of model parameters allows insights that are unobtainable from real datasets. Further, reconstructing transmission networks for fast-evolving viruses like Human Immunodeficiency Virus (HIV) may have the potential to greatly enhance epidemic intervention, but transmission network reconstruction methods have been inadequately studied, largely because it is difficult to obtain 'truth' sets on which to test them and properly measure their performance.ResultsWe introduce FrAmework for VIral Transmission and Evolution Simulation (FAVITES), a robust framework for simulating realistic datasets for epidemics that are caused by fast-evolving pathogens like HIV. FAVITES creates a generative model to produce contact networks, transmission networks, phylogenetic trees and sequence datasets, and to add error to the data. FAVITES is designed to be extensible by dividing the generative model into modules, each of which is expressed as a fixed API that can be implemented using various models. We use FAVITES to simulate HIV datasets and study the realism of the simulated datasets. We then use the simulated data to study the impact of the increased treatment efforts on epidemiological outcomes. We also study two transmission network reconstruction methods and their effectiveness in detecting fast-growing clusters.Availability and implementationFAVITES is available at https://github.com/niemasd/FAVITES, and a Docker image can be found on DockerHub (https://hub.docker.com/r/niemasd/favites).Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC6931354 | biostudies-literature
Project description:?-Lactamase enzymes have attracted substential medical attention from researchers and clinicians because of their clinical, ecological, and evolutionary interest. Here, we present a comprehensive online database of ?-lactamase enzymes. The current database is manually curated and incorporates the primary amino acid sequences, closest structural information in an external structure database (the Protein Data Bank [PDB]) and the functional profiles and phylogenetic trees of the four molecular classes (A, B, C, and D) of ?-lactamases. The functional profiles are presented according to the MICs and kinetic parameters that make them more useful for the investigators. Here, a total of 1,147 ?-lactam resistance genes are analyzed and described in the database. The database is implemented in MySQL and the related website is developed with Zend Framework 2 on an Apache server, supporting all major web browsers. Users can easily retrieve and visualize biologically important information using a set of efficient queries from a graphical interface. This database is freely accessible at http://ifr48.timone.univ-mrs.fr/beta-lactamase/public/.
| S-EPMC6496087 | biostudies-literature
Project description:MotivationClustering is a fundamental task in the analysis of nucleotide sequences. Despite the exponential increase in the size of sequence databases of homologous genes, few methods exist to cluster divergent sequences. Traditional clustering methods have mostly focused on optimizing high speed clustering of highly similar sequences. We develop a phylogenetic clustering method which infers ancestral sequences for a set of initial clusters and then uses a greedy algorithm to cluster sequences.ResultsWe describe a clustering program AncestralClust, which is developed for clustering divergent sequences. We compare this method with other state-of-the-art clustering methods using datasets of homologous sequences from different species. We show that, in divergent datasets, AncestralClust has higher accuracy and more even cluster sizes than current popular methods.Availability and implementationAncestralClust is an Open Source program available at https://github.com/lpipes/ancestralclust.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC8756197 | biostudies-literature
Project description:SUMMARY:Here we present Zombi, a tool to simulate the evolution of species, genomes and sequences in silico, that considers for the first time the evolution of genomes in extinct lineages. It also incorporates various features that have not to date been combined in a single simulator, such as the possibility of generating species trees with a pre-defined variation of speciation and extinction rates through time, simulating explicitly intergenic sequences of variable length and outputting gene tree-species tree reconciliations. AVAILABILITY AND IMPLEMENTATION:Source code and manual are freely available in https://github.com/AADavin/ZOMBI/. SUPPLEMENTARY INFORMATION:Supplementary data are available at Bioinformatics online.
| S-EPMC7031779 | biostudies-literature
Project description:Transmission events are the fundamental building blocks of the dynamics of any infectious disease. Much about the epidemiology of a disease can be learned when these individual transmission events are known or can be estimated. Such estimations are difficult and generally feasible only when detailed epidemiological data are available. The genealogy estimated from genetic sequences of sampled pathogens is another rich source of information on transmission history. Optimal inference of transmission events calls for the combination of genetic data and epidemiological data into one joint analysis. A key difficulty is that the transmission tree, which describes the transmission events between infected hosts, differs from the phylogenetic tree, which describes the ancestral relationships between pathogens sampled from these hosts. The trees differ both in timing of the internal nodes and in topology. These differences become more pronounced when a higher fraction of infected hosts is sampled. We show how the phylogenetic tree of sampled pathogens is related to the transmission tree of an outbreak of an infectious disease, by the within-host dynamics of pathogens. We provide a statistical framework to infer key epidemiological and mutational parameters by simultaneously estimating the phylogenetic tree and the transmission tree. We test the approach using simulations and illustrate its use on an outbreak of foot-and-mouth disease. The approach unifies existing methods in the emerging field of phylodynamics with transmission tree reconstruction methods that are used in infectious disease epidemiology.
| S-EPMC3813836 | biostudies-other
Project description:The body of DNA sequence data lacking taxonomically informative sequence headers is rapidly growing in user and public databases (e.g. sequences lacking identification and contaminants). In the context of systematics studies, sorting such sequence data for taxonomic curation and/or molecular diversity characterization (e.g. crypticism) often requires the building of exploratory phylogenetic trees with reference taxa. The subsequent step of segregating DNA sequences of interest based on observed topological relationships can represent a challenging task, especially for large datasets.We have written TREE2FASTA, a Perl script that enables and expedites the sorting of FASTA-formatted sequence data from exploratory phylogenetic trees. TREE2FASTA takes advantage of the interactive, rapid point-and-click color selection and/or annotations of tree leaves in the popular Java tree-viewer FigTree to segregate groups of FASTA sequences of interest to separate files. TREE2FASTA allows for both simple and nested segregation designs to facilitate the simultaneous preparation of multiple data sets that may overlap in sequence content.
| S-EPMC5838971 | biostudies-literature
Project description:The computational investigation of DNA binding motifs from binding sites is one of the classic tasks in bioinformatics and a prerequisite for understanding gene regulation as a whole. Due to the development of sequencing technologies and the increasing number of available genomes, approaches based on phylogenetic footprinting become increasingly attractive. Phylogenetic footprinting requires phylogenetic trees with attached substitution probabilities for quantifying the evolution of binding sites, but these trees and substitution probabilities are typically not known and cannot be estimated easily.Here, we investigate the influence of phylogenetic trees with different substitution probabilities on the classification performance of phylogenetic footprinting using synthetic and real data. For synthetic data we find that the classification performance is highest when the substitution probability used for phylogenetic footprinting is similar to that used for data generation. For real data, however, we typically find that the classification performance of phylogenetic footprinting surprisingly increases with increasing substitution probabilities and is often highest for unrealistically high substitution probabilities close to one. This finding suggests that choosing realistic model assumptions might not always yield optimal predictions in general and that choosing unrealistically high substitution probabilities close to one might actually improve the classification performance of phylogenetic footprinting.The proposed PF is implemented in JAVA and can be downloaded from https://github.com/mgledi/PhyFoo.: martin.nettling@informatik.uni-halle.de.Supplementary data are available at Bioinformatics online.
| S-EPMC5447242 | biostudies-literature
Project description:Bacterial phylogenetic analyses are commonly performed to explore the evolutionary relationships among various bacterial species and genera based on their 16S rRNA gene sequences; however, these results are limited by mosaicism, intragenomic heterogeneity, and difficulties in distinguishing between related species. In this study, we aimed to perform genome-wide comparisons of different bacterial species, namely Escherichia coli, Shigella, Yersinia, Klebsiella, and Neisseria spp., based on their K-mer profiles to construct phylogenetic trees. Pentanucleotide frequency analyses (512 patterns of 5 nucleotides each) were performed to distinguish between highly similar species. Moreover, Escherichia albertii strains were clearly distinguished from E. coli and Shigella, despite being closely related to enterohemorrhagic E. coli in the phylogenetic tree. In addition, our phylogenetic tree of Ipomoea species based on pentamer frequency in chloroplast genomes was correlated with previously reported morphological similarities. Furthermore, a support vector machine clearly classified E. coli and Shigella genomes based on their pentanucleotide profiles. These results suggest that phylogenetic analyses based on penta- or hexamer profiles are a useful methodology for microbial phylogenetic studies. In addition, we introduced an R application, Phy5, which generates a phylogenetic tree based on genome-wide comparisons of pentamer profiles. The online version of Phy5 can be accessed at https://phy5.shinyapps.io/Phy5R/ and its command line version Phy5cli can be downloaded at https://github.com/YoshioNakano2021/phy5.
| S-EPMC10118083 | biostudies-literature
Project description:We present a method to find motifs by simultaneously using the overrepresentation property and the evolutionary conservation property of motifs. This method is applicable to divergent species where alignment is unreliable, which overcomes a major limitation of the current methods. The method has been applied to search regulatory motifs in four yeast species based on ChIP-chip data in Saccharomyces cerevisiae and obtained 20% higher accuracy than the best current methods. We also discovered cis-regulatory elements that govern the tight regulation of ribosomal protein genes in two distantly related insects by using this method. These results demonstrate that our method will be useful for the extraction of regulatory signals in multiple genomes.
| S-EPMC1160516 | biostudies-literature