Sampling and Summarizing Transmission Trees with Multi-strain Infections

Overview

Journal Bioinformatics

Publisher Oxford University Press

Specialty Biology

Date 2020 Jul 14

PMID 32657399

Citations 5

Authors

Palash Sashittal

Mohammed El-Kebir

Affiliations

Soon will be listed here.

Abstract

Motivation: The combination of genomic and epidemiological data holds the potential to enable accurate pathogen transmission history inference. However, the inference of outbreak transmission histories remains challenging due to various factors such as within-host pathogen diversity and multi-strain infections. Current computational methods ignore within-host diversity and/or multi-strain infections, often failing to accurately infer the transmission history. Thus, there is a need for efficient computational methods for transmission tree inference that accommodate the complexities of real data.

Results: We formulate the direct transmission inference (DTI) problem for inferring transmission trees that support multi-strain infections given a timed phylogeny and additional epidemiological data. We establish hardness for the decision and counting version of the DTI problem. We introduce Transmission Tree Uniform Sampler (TiTUS), a method that uses SATISFIABILITY to almost uniformly sample from the space of transmission trees. We introduce criteria that prioritize parsimonious transmission trees that we subsequently summarize using a novel consensus tree approach. We demonstrate TiTUS's ability to accurately reconstruct transmission trees on simulated data as well as a documented HIV transmission chain.

Availability And Implementation: https://github.com/elkebir-group/TiTUS.

Supplementary Information: Supplementary data are available at Bioinformatics online.

Citing Articles

The tree labeling polytope: a unified approach to ancestral reconstruction problems.

Schmidt H, Raphael B bioRxiv. 2025; .

PMID: 40027631 PMC: 11870558. DOI: 10.1101/2025.02.14.638328.

Evaluating methods for identifying and quantifying co-colonization using next-generation sequencing data.

Hackman J, Hibberd M, Swarthout T, Hinds J, Ashall J, Sheppard C Microbiol Spectr. 2024; :e0364323.

PMID: 39499074 PMC: 11619295. DOI: 10.1128/spectrum.03643-23.

Joint inference of cell lineage and mitochondrial evolution from single-cell sequencing data.

Sashittal P, Chen V, Pasarkar A, Raphael B Bioinformatics. 2024; 40(Suppl 1):i218-i227.

PMID: 38940122 PMC: 11211840. DOI: 10.1093/bioinformatics/btae231.

Inference of Infectious Disease Transmission through a Relaxed Bottleneck Using Multiple Genomes Per Host.

Carson J, Keeling M, Wyllie D, Ribeca P, Didelot X Mol Biol Evol. 2024; 41(1).

PMID: 38168711 PMC: 10798190. DOI: 10.1093/molbev/msad288.

SOPHIE: Viral outbreak investigation and transmission history reconstruction in a joint phylogenetic and network theory framework.

Skums P, Mohebbi F, Tsyvina V, Baykal P, Nemira A, Ramachandran S Cell Syst. 2022; 13(10):844-856.e4.

PMID: 36265470 PMC: 9590096. DOI: 10.1016/j.cels.2022.07.005.

References

Didelot X, Fraser C, Gardy J, Colijn C . Genomic Infectious Disease Epidemiology in Partially Sampled and Ongoing Outbreaks. Mol Biol Evol. 2017; 34(4):997-1007. PMC: 5850352. DOI: 10.1093/molbev/msw275. View

Leitner T, Escanilla D, Franzen C, Uhlen M, Albert J . Accurate reconstruction of a known HIV-1 transmission history by phylogenetic tree analysis. Proc Natl Acad Sci U S A. 1996; 93(20):10864-9. PMC: 38248. DOI: 10.1073/pnas.93.20.10864. View

Romero-Severson E, Skar H, Bulla I, Albert J, Leitner T . Timing and order of transmission events is not directly reflected in a pathogen phylogeny. Mol Biol Evol. 2014; 31(9):2472-82. PMC: 4137707. DOI: 10.1093/molbev/msu179. View

Dellicour S, Baele G, Dudas G, Faria N, Pybus O, Suchard M . Phylodynamic assessment of intervention strategies for the West African Ebola virus outbreak. Nat Commun. 2018; 9(1):2222. PMC: 5993714. DOI: 10.1038/s41467-018-03763-2. View

Bouckaert R, Vaughan T, Barido-Sottani J, Duchene S, Fourment M, Gavryushkina A . BEAST 2.5: An advanced software platform for Bayesian evolutionary analysis. PLoS Comput Biol. 2019; 15(4):e1006650. PMC: 6472827. DOI: 10.1371/journal.pcbi.1006650. View

De Maio N, Wu C, Wilson D . SCOTTI: Efficient Reconstruction of Transmission within Outbreaks with the Structured Coalescent. PLoS Comput Biol. 2016; 12(9):e1005130. PMC: 5040440. DOI: 10.1371/journal.pcbi.1005130. View

Whittle H, Aaby P, Samb B, Jensen H, Bennett J, Simondon F . Effect of subclinical infection on maintaining immunity against measles in vaccinated children in West Africa. Lancet. 1999; 353(9147):98-102. DOI: 10.1016/S0140-6736(98)02364-2. View

Ypma R, van Ballegooijen W, Wallinga J . Relating phylogenetic trees to transmission trees of infectious disease outbreaks. Genetics. 2013; 195(3):1055-62. PMC: 3813836. DOI: 10.1534/genetics.113.154856. View

El-Kebir M, Satas G, Raphael B . Inferring parsimonious migration histories for metastatic cancers. Nat Genet. 2018; 50(5):718-726. PMC: 6103651. DOI: 10.1038/s41588-018-0106-z. View

10.

Wearing H, Rohani P . Estimating the duration of pertussis immunity using epidemiological signatures. PLoS Pathog. 2009; 5(10):e1000647. PMC: 2763266. DOI: 10.1371/journal.ppat.1000647. View

11.

Vrancken B, Rambaut A, Suchard M, Drummond A, Baele G, Derdelinckx I . The genealogical population dynamics of HIV-1 in a large transmission chain: bridging within and among host evolutionary rates. PLoS Comput Biol. 2014; 10(4):e1003505. PMC: 3974631. DOI: 10.1371/journal.pcbi.1003505. View

12.

De Maio N, Worby C, Wilson D, Stoesser N . Bayesian reconstruction of transmission within outbreaks using genomic variants. PLoS Comput Biol. 2018; 14(4):e1006117. PMC: 5927459. DOI: 10.1371/journal.pcbi.1006117. View

13.

Didelot X, Gardy J, Colijn C . Bayesian inference of infectious disease transmission from whole-genome sequence data. Mol Biol Evol. 2014; 31(7):1869-79. PMC: 4069612. DOI: 10.1093/molbev/msu121. View

14.

Snitkin E, Zelazny A, Thomas P, Stock F, Henderson D, Palmore T . Tracking a hospital outbreak of carbapenem-resistant Klebsiella pneumoniae with whole-genome sequencing. Sci Transl Med. 2012; 4(148):148ra116. PMC: 3521604. DOI: 10.1126/scitranslmed.3004129. View

15.

Lemey P, Derdelinckx I, Rambaut A, Van Laethem K, Dumont S, Vermeulen S . Molecular footprint of drug-selective pressure in a human immunodeficiency virus transmission chain. J Virol. 2005; 79(18):11981-9. PMC: 1212611. DOI: 10.1128/JVI.79.18.11981-11989.2005. View

16.

Cottam E, Thebaud G, Wadsworth J, Gloster J, Mansley L, Paton D . Integrating genetic and epidemiological data to determine transmission pathways of foot-and-mouth disease virus. Proc Biol Sci. 2008; 275(1637):887-95. PMC: 2599933. DOI: 10.1098/rspb.2007.1442. View

17.

Hall M, Colijn C . Transmission Trees on a Known Pathogen Phylogeny: Enumeration and Sampling. Mol Biol Evol. 2019; 36(6):1333-1343. PMC: 6526902. DOI: 10.1093/molbev/msz058. View

18.

Stamatakis A . RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies. Bioinformatics. 2014; 30(9):1312-3. PMC: 3998144. DOI: 10.1093/bioinformatics/btu033. View

19.

Kenah E, Britton T, Halloran M, Longini Jr I . Molecular Infectious Disease Epidemiology: Survival Analysis and Algorithms Linking Phylogenies to Transmission Trees. PLoS Comput Biol. 2016; 12(4):e1004869. PMC: 4829193. DOI: 10.1371/journal.pcbi.1004869. View

20.

Sobel Leonard A, Weissman D, Greenbaum B, Ghedin E, Koelle K . Transmission Bottleneck Size Estimation from Pathogen Deep-Sequencing Data, with an Application to Human Influenza A Virus. J Virol. 2017; 91(14). PMC: 5487570. DOI: 10.1128/JVI.00171-17. View