{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:25:56Z","timestamp":1773275156555,"version":"3.50.1"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["NSF"],"award-info":[{"award-number":["NSF"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["2006069"],"award-info":[{"award-number":["2006069"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["1458652"],"award-info":[{"award-number":["1458652"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["OCI-0725070"],"award-info":[{"award-number":["OCI-0725070"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["ACI-1238993"],"award-info":[{"award-number":["ACI-1238993"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"State of Illinois, and as of December 2019, the National Geospatial-Intelligence Agency"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Summary<\/jats:title>\n                  <jats:p>Multiple sequence alignment is an initial step in many bioinformatics pipelines, including phylogeny estimation, protein structure prediction and taxonomic identification of reads produced in amplicon or metagenomic datasets, etc. Yet, alignment estimation is challenging on datasets that exhibit substantial sequence length heterogeneity, and especially when the datasets have fragmentary sequences as a result of including reads or contigs generated by next-generation sequencing technologies. Here, we examine techniques that have been developed to improve alignment estimation when datasets contain substantial numbers of fragmentary sequences. We find that MAGUS, a recently developed MSA method, is fairly robust to fragmentary sequences under many conditions, and that using a two-stage approach where MAGUS is used to align selected \u2018backbone sequences\u2019 and the remaining sequences are added into the alignment using ensembles of Hidden Markov Models further improves alignment accuracy. The combination of MAGUS with the ensemble of eHMMs (i.e. MAGUS+eHMMs) clearly improves on UPP, the previous leading method for aligning datasets with high levels of fragmentation.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>UPP is available on https:\/\/github.com\/smirarab\/sepp, and MAGUS is available on https:\/\/github.com\/vlasmirnov\/MAGUS. MAGUS+eHMMs can be performed by running MAGUS to obtain the backbone alignment, and then using the backbone alignment as an input to UPP.<\/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\/btab788","type":"journal-article","created":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T20:11:54Z","timestamp":1636747914000},"page":"918-924","source":"Crossref","is-referenced-by-count":17,"title":["MAGUS+eHMMs: improved multiple sequence alignment accuracy for fragmentary sequences"],"prefix":"10.1093","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2276-9892","authenticated-orcid":false,"given":"Chengze","family":"Shen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3550-2636","authenticated-orcid":false,"given":"Paul","family":"Zaharias","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7717-3514","authenticated-orcid":false,"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61801, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"2023020108522015700_btab788-B1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-3-2","article-title":"The Comparative RNA Web (CRW) Site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs","volume":"3","author":"Cannone","year":"2002","journal-title":"BMC Bioinformatics"},{"key":"2023020108522015700_btab788-B2","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"Muscle: multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020108522015700_btab788-B3","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.sbi.2006.04.004","article-title":"Multiple sequence alignment","volume":"16","author":"Edgar","year":"2006","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020108522015700_btab788-B4","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1093\/molbev\/msp274","article-title":"Bayesian inference of species trees from multilocus data","volume":"27","author":"Heled","year":"2010","journal-title":"Mol. Biol. Evol"},{"key":"2023020108522015700_btab788-B5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-0716-1036-7","volume-title":"Multiple Sequence Alignment: Methods and Protocols","author":"Katoh","year":"2021"},{"key":"2023020108522015700_btab788-B6","doi-asserted-by":"crossref","first-page":"3144","DOI":"10.1093\/bioinformatics\/bts578","article-title":"Adding unaligned sequences into an existing alignment using MAFFT and LAST","volume":"28","author":"Katoh","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B7","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1093\/molbev\/mst010","article-title":"MAFFT Multiple Sequence Alignment Software Version 7: improvements in performance and usability","volume":"30","author":"Katoh","year":"2013","journal-title":"Mol. Biol. Evol"},{"key":"2023020108522015700_btab788-B8","first-page":"106","author":"Kececioglu","year":"1993"},{"key":"2023020108522015700_btab788-B9","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1126\/science.1171243","article-title":"Rapid and accurate large-scale coestimation of sequence alignments and phylogenetic trees","volume":"324","author":"Liu","year":"2009","journal-title":"Science"},{"key":"2023020108522015700_btab788-B10","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1093\/sysbio\/syr095","article-title":"SAT\u00e9-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees","volume":"61","author":"Liu","year":"2012","journal-title":"Syst. Biol"},{"key":"2023020108522015700_btab788-B11","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1186\/1471-2105-11-538","article-title":"pplacer: linear time maximum-likelihood and Bayesian phylogenetic placement of sequences onto a fixed reference tree","volume":"11","author":"Matsen","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020108522015700_btab788-B12","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1093\/bioinformatics\/btr553","article-title":"FASTSP: linear time calculation of alignment accuracy","volume":"27","author":"Mirarab","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B13","first-page":"247","article-title":"SEPP: SAT\u00e9-enabled phylogenetic placement","author":"Mirarab","year":"2012","journal-title":"Pac. Symp. Biocomput"},{"key":"2023020108522015700_btab788-B14","author":"Mirarab","year":"2015"},{"key":"2023020108522015700_btab788-B15","doi-asserted-by":"crossref","first-page":"3548","DOI":"10.1093\/bioinformatics\/btu721","article-title":"TIPP: taxonomic identification and phylogenetic profiling","volume":"30","author":"Nguyen","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B16","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1186\/s12864-016-3097-0","article-title":"HIPPI: highly accurate protein family classification with ensembles of HMMs","volume":"17","author":"Nguyen","year":"2016","journal-title":"BMC Genomics"},{"key":"2023020108522015700_btab788-B17","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1186\/s13059-015-0688-z","article-title":"Ultra-large alignments using phylogeny-aware profiles","volume":"16","author":"Nguyen","year":"2015","journal-title":"Genome Biol"},{"key":"2023020108522015700_btab788-B18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-7-471","article-title":"The accuracy of several multiple sequence alignment programs for proteins","volume":"7","author":"Nuin","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023020108522015700_btab788-B19","doi-asserted-by":"crossref","first-page":"e9490","DOI":"10.1371\/journal.pone.0009490","article-title":"FastTree 2 \u2013 approximately maximum-likelihood trees for large alignments","volume":"5","author":"Price","year":"2010","journal-title":"PLoS One"},{"key":"2023020108522015700_btab788-B20","doi-asserted-by":"crossref","first-page":"1839","DOI":"10.1093\/bioinformatics\/btab023","article-title":"TIPP2: metagenomic taxonomic profiling using phylogenetic markers","volume":"37","author":"Shah","year":"2021","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B21","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/msb.2011.75","article-title":"Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega","volume":"7","author":"Sievers","year":"2011","journal-title":"Mol. Syst. Biol"},{"key":"2023020108522015700_btab788-B22","author":"Smirnov","year":"2021"},{"key":"2023020108522015700_btab788-B23","doi-asserted-by":"crossref","first-page":"1666","DOI":"10.1093\/bioinformatics\/btaa992","article-title":"MAGUS: multiple sequence Alignment using Graph clUStering","volume":"37","author":"Smirnov","year":"2020","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B24","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1093\/sysbio\/syaa058","article-title":"Phylogeny estimation given sequence length heterogeneity","volume":"70","author":"Smirnov","year":"2020","journal-title":"Syst. Biol"},{"key":"2023020108522015700_btab788-B25","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":"2023020108522015700_btab788-B26","first-page":"157","article-title":"Rose: generating sequence families","volume":"14","author":"Stoye","year":"1998","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023020108522015700_btab788-B27","author":"Van Dongen","year":"2000"},{"key":"2023020108522015700_btab788-B28","author":"Van Dongen","year":"2000"},{"key":"2023020108522015700_btab788-B29","doi-asserted-by":"crossref","first-page":"i559","DOI":"10.1093\/bioinformatics\/btm226","article-title":"Multiple alignment by aligning alignments","volume":"23","author":"Wheeler","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020108522015700_btab788-B30","volume-title":"Algorithms for Computational Biology (AlCoB 2021), Vol. 12715. Lecture Notes in Computer Science","author":"Zaharias","year":"2021"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab788\/41382259\/btab788.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/918\/49008313\/btab788.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/918\/49008313\/btab788.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T20:11:41Z","timestamp":1675282301000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/4\/918\/6430102"}},"subtitle":[],"editor":[{"given":"Valentina","family":"Boeva","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab788","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,2,15]]},"published":{"date-parts":[[2021,11,17]]}}}