{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T00:56:32Z","timestamp":1774400192888,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"vor","delay-in-days":11,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DGE-1650604"],"award-info":[{"award-number":["DGE-1650604"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["R35GM125055"],"award-info":[{"award-number":["R35GM125055"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Alfred P. Sloan Research Fellowship"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Admixture, the interbreeding between previously distinct populations, is a pervasive force in evolution. The evolutionary history of populations in the presence of admixture can be modeled by augmenting phylogenetic trees with additional nodes that represent admixture events. While enabling a more faithful representation of evolutionary history, admixture graphs present formidable inferential challenges, and there is an increasing need for methods that are accurate, fully automated and computationally efficient. One key challenge arises from the size of the space of admixture graphs. Given that exhaustively evaluating all admixture graphs can be prohibitively expensive, heuristics have been developed to enable efficient search over this space. One heuristic, implemented in the popular method TreeMix, consists of adding edges to a starting tree while optimizing a suitable objective function.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Here, we present a demographic model (with one admixed population incident to a leaf) where TreeMix and any other starting-tree-based maximum likelihood heuristic using its likelihood function is guaranteed to get stuck in a local optimum and return an incorrect network topology. To address this issue, we propose a new search strategy that we term maximum likelihood network orientation (MLNO). We augment TreeMix with an exhaustive search for an MLNO, referring to this approach as OrientAGraph. In evaluations including previously published admixture graphs, OrientAGraph outperformed TreeMix on 4\/8 models (there are no differences in the other cases). Overall, OrientAGraph found graphs with higher likelihood scores and topological accuracy while remaining computationally efficient. Lastly, our study reveals several directions for improving maximum likelihood admixture graph estimation.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>OrientAGraph is available on Github (https:\/\/github.com\/sriramlab\/OrientAGraph) under the GNU General Public License v3.0.<\/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\/btab267","type":"journal-article","created":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T20:04:18Z","timestamp":1619121858000},"page":"i142-i150","source":"Crossref","is-referenced-by-count":41,"title":["Advancing admixture graph estimation via maximum likelihood network orientation"],"prefix":"10.1093","volume":"37","author":[{"given":"Erin K","family":"Molloy","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California , Los Angeles, LA 90095, USA"},{"name":"Institute for Advanced Computer Studies, University of Maryland , College Park, College Park, MD 20740, USA"}]},{"given":"Arun","family":"Durvasula","sequence":"additional","affiliation":[{"name":"Department of Human Genetics, David Geffen School of Medicine, University of California , Los Angeles, LA 90095, USA"}]},{"given":"Sriram","family":"Sankararaman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California , Los Angeles, LA 90095, USA"},{"name":"Department of Human Genetics, David Geffen School of Medicine, University of California , Los Angeles, LA 90095, USA"},{"name":"Bioinformatics Interdepartmental Program, University of California , Los Angeles, LA 90095, USA"},{"name":"Department of Computational Medicine, University of California , Los Angeles, LA 90095, USA"}]}],"member":"286","published-online":{"date-parts":[[2021,7,12]]},"reference":[{"key":"2023062410164325300_btab267-B1","first-page":"21:1","volume-title":"19th International Workshop on Algorithms in Bioinformatics, WABI 2019, September 8\u201310, 2019","author":"Cao","year":"2019"},{"key":"2023062410164325300_btab267-B2","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1126\/science.aaw2090","article-title":"Genomic architecture and introgression shape a butterfly radiation","volume":"366","author":"Edelman","year":"2019","journal-title":"Science"},{"key":"2023062410164325300_btab267-B3","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1093\/sysbio\/syv037","article-title":"Which phylogenetic networks are merely trees with additional arcs?","volume":"64","author":"Francis","year":"2015","journal-title":"Syst. Biol"},{"key":"2023062410164325300_btab267-B4","doi-asserted-by":"crossref","first-page":"1250004","DOI":"10.1142\/S0219720012500047","article-title":"Quartets and unrooted phylogenetic networks","volume":"10","author":"Gambette","year":"2012","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023062410164325300_btab267-B5","doi-asserted-by":"crossref","first-page":"e1005611","DOI":"10.1371\/journal.pcbi.1005611","article-title":"Rearrangement moves on rooted phylogenetic networks","volume":"13","author":"Gambette","year":"2017","journal-title":"PLoS Comput. Biol"},{"key":"2023062410164325300_btab267-B6","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1126\/science.1188021","article-title":"A draft sequence of the neandertal genome","volume":"328","author":"Green","year":"2010","journal-title":"Science"},{"key":"2023062410164325300_btab267-B7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1038\/nature14317","article-title":"Massive migration from the steppe was a source for Indo-European languages in Europe","volume":"522","author":"Haak","year":"2015","journal-title":"Nature"},{"key":"2023062410164325300_btab267-B8","doi-asserted-by":"crossref","DOI":"10.1093\/genetics\/iyaa045","article-title":"Assessing the performance of qpAdm: a statistical tool for studying population admixture","volume":"217","author":"Harney","year":"2021","journal-title":"Genetics"},{"key":"2023062410164325300_btab267-B9","article-title":"Rooting for phylogenetic networks","author":"Huber","year":"2019","journal-title":"arXiv"},{"key":"2023062410164325300_btab267-B10","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under a Wright-Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023062410164325300_btab267-B11","doi-asserted-by":"crossref","first-page":"2177","DOI":"10.1007\/s11538-018-0452-0","article-title":"Exploring the tiers of rooted phylogenetic network space using tail moves","volume":"80","author":"Janssen","year":"2018","journal-title":"Bull. Math. Biol"},{"key":"2023062410164325300_btab267-B12","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-030-25005-8_24","volume-title":"Combinatorial Algorithms","author":"Jansson","year":"2019"},{"key":"2023062410164325300_btab267-B13","doi-asserted-by":"crossref","first-page":"1738","DOI":"10.1093\/bioinformatics\/btx048","article-title":"admixturegraph: an R package for admixture graph manipulation and fitting","volume":"33","author":"Lepp\u00e4l\u00e4","year":"2017","journal-title":"Bioinformatics"},{"key":"2023062410164325300_btab267-B14","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1111\/1755-0998.13230","article-title":"Applying f4-statistics and admixture graphs: theory and examples","volume":"20","author":"Lipson","year":"2020","journal-title":"Mol. Ecol. Resour"},{"key":"2023062410164325300_btab267-B15","doi-asserted-by":"crossref","first-page":"1788","DOI":"10.1093\/molbev\/mst099","article-title":"Efficient moment-based inference of admixture parameters and sources of gene flow","volume":"30","author":"Lipson","year":"2013","journal-title":"Mol. Biol. Evol"},{"key":"2023062410164325300_btab267-B16","doi-asserted-by":"crossref","first-page":"4689","DOI":"10.1038\/ncomms5689","article-title":"Reconstructing Austronesian population history in Island Southeast Asia","volume":"5","author":"Lipson","year":"2014","journal-title":"Nat. Commun"},{"key":"2023062410164325300_btab267-B17","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1038\/nature18964","article-title":"The Simons Genome Diversity Project: 300 genomes from 142 diverse populations","volume":"538","author":"Mallick","year":"2016","journal-title":"Nature"},{"key":"2023062410164325300_btab267-B18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s00026-015-0260-2","article-title":"Counting phylogenetic networks","volume":"19","author":"McDiarmid","year":"2015","journal-title":"Ann. Combinat"},{"key":"2023062410164325300_btab267-B19","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1534\/genetics.112.145037","article-title":"Ancient admixture in human history","volume":"192","author":"Patterson","year":"2012","journal-title":"Genetics"},{"key":"2023062410164325300_btab267-B20","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1534\/genetics.115.183913","article-title":"Admixture, population structure, and F-statistics","volume":"202","author":"Peter","year":"2016","journal-title":"Genetics"},{"key":"2023062410164325300_btab267-B21","doi-asserted-by":"crossref","first-page":"e1002967","DOI":"10.1371\/journal.pgen.1002967","article-title":"Inference of population splits and mixtures from genome-wide allele frequency data","volume":"8","author":"Pickrell","year":"2012","journal-title":"PLoS Genet"},{"key":"2023062410164325300_btab267-B22","doi-asserted-by":"crossref","first-page":"17328","DOI":"10.1038\/s41598-019-53492-9","article-title":"Global phylogeographic and admixture patterns in grey wolves and genetic legacy of an Ancient Siberian lineage","volume":"9","author":"Pilot","year":"2019","journal-title":"Sci. Rep"},{"key":"2023062410164325300_btab267-B23","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol"},{"key":"2023062410164325300_btab267-B24","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","year":"2015","journal-title":"Nature"},{"key":"2023062410164325300_btab267-B25","doi-asserted-by":"crossref","first-page":"735","DOI":"10.1093\/sysbio\/syy015","article-title":"Inferring phylogenetic networks using PhyloNet","volume":"67","author":"Wen","year":"2018","journal-title":"System. Biol"},{"key":"2023062410164325300_btab267-B26","doi-asserted-by":"crossref","first-page":"i326","DOI":"10.1093\/bioinformatics\/btaa465","article-title":"Inference of population admixture network from local gene genealogies: a coalescent-based maximum likelihood approach","volume":"36","author":"Wu","year":"2020","journal-title":"Bioinformatics"},{"key":"2023062410164325300_btab267-B27","first-page":"btaa988","article-title":"miqoGraph: fitting admixture graphs using mixed-integer quadratic optimization","author":"Yan","year":"2020","journal-title":"Bioinformatics"},{"key":"2023062410164325300_btab267-B28","doi-asserted-by":"crossref","first-page":"16448","DOI":"10.1073\/pnas.1407950111","article-title":"Maximum likelihood inference of reticulate evolutionary histories","volume":"111","author":"Yu","year":"2014","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/Supplement_1\/i142\/50694037\/btab267.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/Supplement_1\/i142\/50694037\/btab267.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T20:14:30Z","timestamp":1687637670000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/Supplement_1\/i142\/6319689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,1]]},"references-count":28,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2021,8,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab267","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2021.02.02.429467","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":[[2021,7,1]]},"published":{"date-parts":[[2021,7,1]]}}}