Phylogenetic Clustering by Linear Integer Programming (PhyCLIP)
Open Access
- 11 March 2019
- journal article
- research article
- Published by Oxford University Press (OUP) in Molecular Biology and Evolution
- Vol. 36 (7), 1580-1595
- https://doi.org/10.1093/molbev/msz053
Abstract
Subspecies nomenclature systems of pathogens are increasingly based on sequence data. The use of phylogenetics to identify and differentiate between clusters of genetically similar pathogens is particularly prevalent in virology from the nomenclature of human papillomaviruses to highly pathogenic avian influenza (HPAI) H5Nx viruses. These nomenclature systems rely on absolute genetic distance thresholds to define the maximum genetic divergence tolerated between viruses designated as closely related. However, the phylogenetic clustering methods used in these nomenclature systems are limited by the arbitrariness of setting intra and intercluster diversity thresholds. The lack of a consensus ground truth to define well-delineated, meaningful phylogenetic subpopulations amplifies the difficulties in identifying an informative distance threshold. Consequently, phylogenetic clustering often becomes an exploratory, ad hoc exercise. Phylogenetic Clustering by Linear Integer Programming (PhyCLIP) was developed to provide a statistically principled phylogenetic clustering framework that negates the need for an arbitrarily defined distance threshold. Using the pairwise patristic distance distributions of an input phylogeny, PhyCLIP parameterizes the intra and intercluster divergence limits as statistical bounds in an integer linear programming model which is subsequently optimized to cluster as many sequences as possible. When applied to the hemagglutinin phylogeny of HPAI H5Nx viruses, PhyCLIP was not only able to recapitulate the current WHO/OIE/FAO H5 nomenclature system but also further delineated informative higher resolution clusters that capture geographically distinct subpopulations of viruses. PhyCLIP is pathogen-agnostic and can be generalized to a wide variety of research questions concerning the identification of biologically informative clusters in pathogen phylogenies. PhyCLIP is freely available at http://github.com/alvinxhan/PhyCLIP, last accessed March 15, 2019.Keywords
Funding Information
- A*STAR Graduate Scholarship programme
- Gates Cambridge Trust (OPP1144)
- A*STAR HEIDI programme (H1699f0013)
- Bioinformatics Institute
- University Research Fellowship
This publication has 50 references indexed in Scilit:
- Automated analysis of phylogenetic clustersBMC Bioinformatics, 2013
- Proposals for the classification of human rhinovirus species A, B and C into genotypically assigned typesJournal of General Virology, 2013
- Simple Epidemiological Dynamics Explain Phylogenetic Clustering of HIV from Patients with Recent InfectionPLoS Computational Biology, 2012
- Toward Genetics-Based Virus Taxonomy: Comparative Analysis of a Genetics-Based Classification and the Taxonomy of PicornavirusesJournal of Virology, 2012
- Statistics and Truth in PhylogenomicsMolecular Biology and Evolution, 2011
- Survey of Branch Support Methods Demonstrates Accuracy, Power, and Robustness of Fast Likelihood-based Approximation SchemesSystematic Biology, 2011
- Papillomaviruses: evolution, Linnaean taxonomy and current nomenclatureTrends in Microbiology, 2011
- The Threshold Bootstrap Clustering: A New Approach to Find Families or Transmission Clusters within Molecular QuasispeciesPLOS ONE, 2010
- The development and genetic diversity of H5N1 influenza virus in China, 1996–2006Virology, 2008
- Identification of the Progenitors of Indonesian and Vietnamese Avian Influenza A (H5N1) Viruses from Southern ChinaJournal of Virology, 2008