{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T20:57:43Z","timestamp":1780606663952,"version":"3.54.1"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":12,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 18-50502"],"award-info":[{"award-number":["CCF 18-50502"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2027669"],"award-info":[{"award-number":["CCF-2027669"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>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\u2019s ability to accurately reconstruct transmission trees on simulated data as well as a documented HIV transmission chain.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>https:\/\/github.com\/elkebir-group\/TiTUS.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa438","type":"journal-article","created":{"date-parts":[[2020,5,2]],"date-time":"2020-05-02T15:09:09Z","timestamp":1588432149000},"page":"i362-i370","source":"Crossref","is-referenced-by-count":11,"title":["Sampling and summarizing transmission trees with multi-strain infections"],"prefix":"10.1093","volume":"36","author":[{"given":"Palash","family":"Sashittal","sequence":"first","affiliation":[{"name":"Department of Aerospace Engineering, University of Illinois at Urbana-Champaign , Urbama, IL 61801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign , Urbama, IL 61801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"2024021913331033000_btaa438-B1","doi-asserted-by":"crossref","first-page":"i408","DOI":"10.1093\/bioinformatics\/btz312","article-title":"Summarizing the solution space in tumor phylogeny inference by multiple consensus trees","volume":"35","author":"Aguse","year":"2019","journal-title":"Bioinformatics"},{"key":"2024021913331033000_btaa438-B2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/978-3-540-78911-6_3","volume-title":"Mathematical Epidemiology","author":"Allen","year":"2008"},{"key":"2024021913331033000_btaa438-B3","doi-asserted-by":"crossref","first-page":"e1006650","DOI":"10.1371\/journal.pcbi.1006650","article-title":"BEAST 2.5: an advanced software platform for Bayesian evolutionary analysis","volume":"15","author":"Bouckaert","year":"2019","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B4","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/978-3-642-40627-0_18","volume-title":"Principles and Practice of Constraint Programming","author":"Chakraborty","year":"2013"},{"key":"2024021913331033000_btaa438-B5","first-page":"1","author":"Chakraborty","year":"2014"},{"key":"2024021913331033000_btaa438-B6","first-page":"304","author":"Chakraborty","year":"2015"},{"key":"2024021913331033000_btaa438-B7","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1098\/rspb.2007.1442","article-title":"Integrating genetic and epidemiological data to determine transmission pathways of foot-and-mouth disease virus","volume":"275","author":"Cottam","year":"2008","journal-title":"Proc. R. Soc. B Biol. Sci"},{"key":"2024021913331033000_btaa438-B8","author":"Creignou","year":"1993"},{"key":"2024021913331033000_btaa438-B9","doi-asserted-by":"crossref","first-page":"e1005130","DOI":"10.1371\/journal.pcbi.1005130","article-title":"SCOTTI: efficient reconstruction of transmission within outbreaks with the structured coalescent","volume":"12","author":"De Maio","year":"2016","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B10","doi-asserted-by":"crossref","first-page":"e1006117","DOI":"10.1371\/journal.pcbi.1006117","article-title":"Bayesian reconstruction of transmission within outbreaks using genomic variants","volume":"14","author":"De Maio","year":"2018","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B11","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1038\/s41467-018-03763-2","article-title":"Phylodynamic assessment of intervention strategies for the West African Ebola virus outbreak","volume":"9","author":"Dellicour","year":"2018","journal-title":"Nat. Commun"},{"key":"2024021913331033000_btaa438-B12","doi-asserted-by":"crossref","first-page":"1869","DOI":"10.1093\/molbev\/msu121","article-title":"Bayesian inference of infectious disease transmission from whole-genome sequence data","volume":"31","author":"Didelot","year":"2014","journal-title":"Mol. Biol. Evol"},{"key":"2024021913331033000_btaa438-B13","first-page":"997","article-title":"Genomic infectious disease epidemiology in partially sampled and ongoing outbreaks","volume":"34","author":"Didelot","year":"2017","journal-title":"Mol. Biol. Evol"},{"key":"2024021913331033000_btaa438-B34546440","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1038\/s41588-018-0106-z","article-title":"Inferring parsimonious migration histories for metastatic cancers","volume":"50","author":"El-Kebir","year":"2018","journal-title":"Nat. Genet."},{"key":"2024021913331033000_btaa438-B14","first-page":"63","author":"Govek","year":"2018"},{"key":"2024021913331033000_btaa438-B15","doi-asserted-by":"crossref","first-page":"e1004613","DOI":"10.1371\/journal.pcbi.1004613","article-title":"Epidemic reconstruction in a phylogenetics framework: transmission trees as partitions of the node set","volume":"11","author":"Hall","year":"2015","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B16","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1093\/molbev\/msz058","article-title":"Transmission trees on a known pathogen phylogeny: enumeration and sampling","volume":"36","author":"Hall","year":"2019","journal-title":"Mol. Biol. Evol"},{"key":"2024021913331033000_btaa438-B17","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1126\/science.1182395","article-title":"Evolution of MRSA during hospital transmission and intercontinental spread","volume":"327","author":"Harris","year":"2010","journal-title":"Science"},{"key":"2024021913331033000_btaa438-B18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating: Algorithms and Complexity","author":"Jerrum","year":"2003"},{"key":"2024021913331033000_btaa438-B19","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1111\/1755-0998.12676","article-title":"treespace: statistical exploration of landscapes of phylogenetic trees","volume":"17","author":"Jombart","year":"2017","journal-title":"Mol. Ecol. Resour"},{"key":"2024021913331033000_btaa438-B20","first-page":"85","volume-title":"Reducibility among Combinatorial Problems","author":"Karp","year":"1972"},{"key":"2024021913331033000_btaa438-B21","doi-asserted-by":"crossref","first-page":"e1004869","DOI":"10.1371\/journal.pcbi.1004869","article-title":"Molecular infectious disease epidemiology: survival analysis and algorithms linking phylogenies to transmission trees","volume":"12","author":"Kenah","year":"2016","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B22","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1214\/17-STS637","article-title":"Estimating transmission from genetic and epidemiological data: a metric to compare transmission trees","volume":"33","author":"Kendall","year":"2018","journal-title":"Stat. Sci"},{"key":"2024021913331033000_btaa438-B23","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-4149(82)90011-4","article-title":"The coalescent","volume":"13","author":"Kingman","year":"1982","journal-title":"Stoch. Proc. Appl"},{"key":"2024021913331033000_btaa438-B24","doi-asserted-by":"crossref","first-page":"10864","DOI":"10.1073\/pnas.93.20.10864","article-title":"Accurate reconstruction of a known HIV-1 transmission history by phylogenetic tree analysis","volume":"93","author":"Leitner","year":"1996","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2024021913331033000_btaa438-B25","doi-asserted-by":"crossref","first-page":"11981","DOI":"10.1128\/JVI.79.18.11981-11989.2005","article-title":"Molecular footprint of drug-selective pressure in a human immunodeficiency virus transmission chain","volume":"79","author":"Lemey","year":"2005","journal-title":"J. Virol"},{"key":"2024021913331033000_btaa438-B26","first-page":"e00171","article-title":"Transmission bottleneck size estimation from pathogen deep-sequencing data, with an application to human influenza A virus","volume":"91","author":"Leonard","year":"2017","journal-title":"J. Virol"},{"key":"2024021913331033000_btaa438-B27","doi-asserted-by":"crossref","DOI":"10.1201\/b22024","volume-title":"Computational Complexity of Counting and Sampling","author":"Mikl\u00f3s","year":"2019"},{"key":"2024021913331033000_btaa438-B28","doi-asserted-by":"crossref","first-page":"2472","DOI":"10.1093\/molbev\/msu179","article-title":"Timing and order of transmission events is not directly reflected in a pathogen phylogeny","volume":"31","author":"Romero-Severson","year":"2014","journal-title":"Mol. Biol. Evol"},{"key":"2024021913331033000_btaa438-B29","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal mutation trees of sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math"},{"key":"2024021913331033000_btaa438-B30","first-page":"842237","author":"Sashittal","year":"2019"},{"key":"2024021913331033000_btaa438-B31","doi-asserted-by":"publisher","DOI":"10.1093\/cid\/ciaa203","article-title":"Genomic diversity of SARS-CoV-2 in Coronavirus Disease 2019 patients","author":"Shen","year":"2020","journal-title":"Clin. Infect. Dis"},{"key":"2024021913331033000_btaa438-B32","first-page":"813931","author":"Sledzieski","year":"2019"},{"key":"2024021913331033000_btaa438-B33","doi-asserted-by":"crossref","first-page":"148ra116","DOI":"10.1126\/scitranslmed.3004129","article-title":"Tracking a hospital outbreak of carbapenem-resistant Klebsiella pneumoniae with whole-genome sequencing","volume":"4","author":"Snitkin","year":"2012","journal-title":"Sci. Transl. Med"},{"key":"2024021913331033000_btaa438-B34","first-page":"244","author":"Soos","year":"2009"},{"key":"2024021913331033000_btaa438-B35","author":"Soos","year":"2019"},{"key":"2024021913331033000_btaa438-B36","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/bioinformatics\/btu033","article-title":"RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies","volume":"30","author":"Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"2024021913331033000_btaa438-B37","doi-asserted-by":"publisher","DOI":"10.1093\/nsr\/nwaa036.","article-title":"On the origin and continuing evolution of SARS-CoV-2","author":"Tang","year":"2020","journal-title":"Natl. Sci. Rev"},{"key":"2024021913331033000_btaa438-B38","first-page":"424","author":"Thurley","year":"2006"},{"key":"2024021913331033000_btaa438-B39","doi-asserted-by":"crossref","first-page":"e1003505","DOI":"10.1371\/journal.pcbi.1003505","article-title":"The genealogical population dynamics of HIV-1 in a large transmission chain: bridging within and among host evolutionary rates","volume":"10","author":"Vrancken","year":"2014","journal-title":"PLoS Comput. Biol"},{"key":"2024021913331033000_btaa438-B40","doi-asserted-by":"crossref","first-page":"e1000647","DOI":"10.1371\/journal.ppat.1000647","article-title":"Estimating the duration of pertussis immunity using epidemiological signatures","volume":"5","author":"Wearing","year":"2009","journal-title":"PLoS Pathog"},{"key":"2024021913331033000_btaa438-B41","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/S0140-6736(98)02364-2","article-title":"Effect of subclinical infection on maintaining immunity against measles in vaccinated children in west Africa","volume":"353","author":"Whittle","year":"1999","journal-title":"Lancet"},{"key":"2024021913331033000_btaa438-B42","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1093\/molbev\/msx304","article-title":"PHYLOSCANNER: inferring transmission from within- and between-host pathogen genetic diversity","volume":"35","author":"Wymant","year":"2018","journal-title":"Mol. Biol. Evol"},{"key":"2024021913331033000_btaa438-B43","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1098\/rspb.2011.0913","article-title":"Unravelling transmission trees of infectious diseases by combining genetic and epidemiological data","volume":"279","author":"Ypma","year":"2012","journal-title":"Proc. R. Soc. B Biol. Sci"},{"key":"2024021913331033000_btaa438-B44","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.1534\/genetics.113.154856","article-title":"Relating phylogenetic trees to transmission trees of infectious disease outbreaks","volume":"195","author":"Ypma","year":"2013","journal-title":"Genetics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i362\/56702838\/bioinformatics_36_supplement1_i362.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i362\/56702838\/bioinformatics_36_supplement1_i362.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T08:41:28Z","timestamp":1708332088000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_1\/i362\/5870507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":45,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa438","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.03.17.996041","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,7]]},"published":{"date-parts":[[2020,7,1]]}}}