More Like this

1. FastRFS: fast and accurate Robinson-Foulds Supertrees using constrained exact optimization

   https://doi.org/10.1093/bioinformatics/btw600  

   Vachaspati, Pranjal ; Warnow, Tandy ; Chauve, ed., Cedric ( September 2016 , Bioinformatics)

   The estimation of phylogenetic trees is a major part of many biological dataset analyses, but maximum likelihood approaches are NP-hard and Bayesian MCMC methods do not scale well to even moderate-sized datasets. Supertree methods, which are used to construct trees from trees computed on subsets, are critically important tools for enabling the statistical estimation of phylogenies for large and potentially heterogeneous datasets. Supertree estimation is itself NP-hard, and no current supertree method has sufficient accuracy and scalability to provide good accuracy on the large datasets that supertree methods were designed for, containing thousands of species and many subset trees.

   We present FastRFS, a new method based on a dynamic programming method we have developed to find an exact solution to the Robinson-Foulds Supertree problem within a constrained search space. FastRFS has excellent accuracy in terms of criterion scores and topological accuracy of the resultant trees, substantially improving on competing methods on a large collection of biological and simulated data. In addition, FastRFS is extremely fast, finishing in minutes on even very large datasets, and in under an hour on a biological dataset with 2228 species.

   FastRFS is available on github at https://github.com/pranjalv123/FastRFS

   Supplementary data are available at Bioinformatics online.

    

   more » « less
2. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees

   https://doi.org/10.1093/bioinformatics/btz312  

   Aguse, Nuraini ; Qi, Yuanyuan ; El-Kebir, Mohammed ( July 2019 , Bioinformatics)

   Cancer phylogenies are key to studying tumorigenesis and have clinical implications. Due to the heterogeneous nature of cancer and limitations in current sequencing technology, current cancer phylogeny inference methods identify a large solution space of plausible phylogenies. To facilitate further downstream analyses, methods that accurately summarize such a set T of cancer phylogenies are imperative. However, current summary methods are limited to a single consensus tree or graph and may miss important topological features that are present in different subsets of candidate trees.

   We introduce the Multiple Consensus Tree (MCT) problem to simultaneously cluster T and infer a consensus tree for each cluster. We show that MCT is NP-hard, and present an exact algorithm based on mixed integer linear programming (MILP). In addition, we introduce a heuristic algorithm that efficiently identifies high-quality consensus trees, recovering all optimal solutions identified by the MILP in simulated data at a fraction of the time. We demonstrate the applicability of our methods on both simulated and real data, showing that our approach selects the number of clusters depending on the complexity of the solution space T.

   https://github.com/elkebir-group/MCT.

   Supplementary data are available at Bioinformatics online.

    

   more » « less
3. Topiary: Pruning the manual labor from ancestral sequence reconstruction

   https://doi.org/10.1002/pro.4551  

   Orlandi, Kona N. ; Phillips, Sophia R. ; Sailer, Zachary R. ; Harman, Joseph L. ; Harms, Michael J. ( January 2023 , Protein Science)

   Ancestral sequence reconstruction (ASR) is a powerful tool to study the evolution of proteins and thus gain deep insight into the relationships among protein sequence, structure, and function. A major barrier to its broad use is the complexity of the task: it requires multiple software packages, complex file manipulations, and expert phylogenetic knowledge. Here we introducetopiary, a software pipeline that aims to overcome this barrier. To use topiary, users prepare a spreadsheet with a handful of sequences. Topiary then: (1) Infers the taxonomic scope for the ASR study and finds relevant sequences by BLAST; (2) Does taxonomically informed sequence quality control and redundancy reduction; (3) Constructs a multiple sequence alignment; (4) Generates a maximum‐likelihood gene tree; (5) Reconciles the gene tree to the species tree; (6) Reconstructs ancestral amino acid sequences; and (7) Determines branch supports. The pipeline returns annotated evolutionary trees, spreadsheets with sequences, and graphical summaries of ancestor quality. This is achieved by integrating modern phylogenetics software (Muscle5, RAxML‐NG, GeneRax, and PastML) with online databases (NCBI and the Open Tree of Life). In this paper, we introduce non‐expert readers to the steps required for ASR, describe the specific design choices made intopiary, provide a detailed protocol for users, and then validate the pipeline using datasets from a broad collection of protein families. Topiary is freely available for download:https://github.com/harmslab/topiary.

    

   more » « less
4. Morphological Analysis of Size and Shape ( MASS ): An integrative software program for morphometric analyses of leaves

   https://doi.org/10.1002/aps3.11288  

   Chuanromanee, Tya S. ; Cohen, James I. ; Ryan, Gillian L. ( September 2019 , Applications in Plant Sciences)

   Morphometric analysis is a common approach for comparing and categorizing botanical samples; however, completing a suite of analyses using existing tools may require a multi‐stage, multi‐program process. To facilitate streamlined analysis within a single program, Morphological Analysis of Size and Shape (MASS) for leaves was developed. Its utility is demonstrated using exemplar leaf samples fromAcer saccharum,Malus domestica, andLithospermum.

   Exemplar samples were obtained from across a single tree (Acer saccharum), three trees in the same species (Malus domestica), and online, digitized herbarium specimens (Lithospermum).MASSwas used to complete simple geometric measurements of samples, such as length and area, as well as geometric morphological analyses including elliptical Fourier and Procrustes analyses. Principal component analysis (PCA) of data was also completed within the same program.

   MASSis capable of making desired measurements and analyzing traditional morphometric data as well as landmark and outline data.

   UsingMASS, differences were observed among leaves of the three studied taxa, but only inMalus domesticawere differences statistically significant or correlated with other morphological features. In the future,MASScould be applied for analysis of other two‐dimensional organs and structures.MASSis available for download athttps://github.com/gillianlynnryan/MASS.

    

   more » « less
5. MULTICOM2 open-source protein structure prediction system powered by deep learning and distance prediction

   https://doi.org/10.1038/s41598-021-92395-6  

   Wu, Tianqi ; Liu, Jian ; Guo, Zhiye ; Hou, Jie ; Cheng, Jianlin ( June 2021 , Scientific Reports)

   Protein structure prediction is an important problem in bioinformatics and has been studied for decades. However, there are still few open-source comprehensive protein structure prediction packages publicly available in the field. In this paper, we present our latest open-source protein tertiary structure prediction system—MULTICOM2, an integration of template-based modeling (TBM) and template-free modeling (FM) methods. The template-based modeling uses sequence alignment tools with deep multiple sequence alignments to search for structural templates, which are much faster and more accurate than MULTICOM1. The template-free (ab initio or de novo) modeling uses the inter-residue distances predicted by DeepDist to reconstruct tertiary structure models without using any known structure as template. In the blind CASP14 experiment, the average TM-score of the models predicted by our server predictor based on the MULTICOM2 system is 0.720 for 58 TBM (regular) domains and 0.514 for 38 FM and FM/TBM (hard) domains, indicating that MULTICOM2 is capable of predicting good tertiary structures across the board. It can predict the correct fold for 76 CASP14 domains (95% regular domains and 55% hard domains) if only one prediction is made for a domain. The success rate is increased to 3% for both regular and hard domains if five predictions are made per domain. Moreover, the prediction accuracy of the pure template-free structure modeling method on both TBM and FM targets is very close to the combination of template-based and template-free modeling methods. This demonstrates that the distance-based template-free modeling method powered by deep learning can largely replace the traditional template-based modeling method even on TBM targets that TBM methods used to dominate and therefore provides a uniform structure modeling approach to any protein. Finally, on the 38 CASP14 FM and FM/TBM hard domains, MULTICOM2 server predictors (MULTICOM-HYBRID, MULTICOM-DEEP, MULTICOM-DIST) were ranked among the top 20 automated server predictors in the CASP14 experiment. After combining multiple predictors from the same research group as one entry, MULTICOM-HYBRID was ranked no. 5. The source code of MULTICOM2 is freely available athttps://github.com/multicom-toolbox/multicom/tree/multicom_v2.0.

    

   more » « less