{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T04:04:05Z","timestamp":1777521845129,"version":"3.51.4"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T00:00:00Z","timestamp":1673308800000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2006069"],"award-info":[{"award-number":["2006069"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Multiple sequence alignment (MSA) is a basic step in many bioinformatics pipelines. However, achieving highly accurate alignments on large datasets, especially those with sequence length heterogeneity, is a challenging task. Ultra-large multiple sequence alignment using Phylogeny-aware Profiles (UPP) is a method for MSA estimation that builds an ensemble of Hidden Markov Models (eHMM) to represent an estimated alignment on the full-length sequences in the input, and then adds the remaining sequences into the alignment using selected HMMs in the ensemble. Although UPP provides good accuracy, it is computationally intensive on large datasets.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present UPP2, a direct improvement on UPP. The main advance is a fast technique for selecting HMMs in the ensemble that allows us to achieve the same accuracy as UPP but with greatly reduced runtime. We show that UPP2 produces more accurate alignments compared to leading MSA methods on datasets exhibiting substantial sequence length heterogeneity and is among the most accurate otherwise.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/gillichu\/sepp.<\/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\/btad007","type":"journal-article","created":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T13:34:05Z","timestamp":1673357645000},"source":"Crossref","is-referenced-by-count":12,"title":["UPP2: fast and accurate alignment of datasets with fragmentary sequences"],"prefix":"10.1093","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8676-7565","authenticated-orcid":false,"given":"Minhyuk","family":"Park","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61820, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ivanovic","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61820, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gillian","family":"Chu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61820, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2276-9892","authenticated-orcid":false,"given":"Chengze","family":"Shen","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign , Urbana, IL 61820, 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 61820, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,1,10]]},"reference":[{"key":"2023011809302529800_btad007-B1","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1093\/molbev\/mss256","article-title":"Class of multiple sequence alignment algorithm affects genomic analysis","volume":"30","author":"Blackburne","year":"2013","journal-title":"Mol. Biol. Evol"},{"key":"2023011809302529800_btad007-B2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-5-21","article-title":"Sequence embedding for fast construction of guide trees for multiple sequence alignment","volume":"5","author":"Blackshields","year":"2010","journal-title":"Algorithms Mol. Biol"},{"key":"2023011809302529800_btad007-B3","first-page":"339","volume-title":"Contemporary High Performance Computing, Chapman & Hall\/CRC Computational Science","author":"Bode","year":"2013"},{"key":"2023011809302529800_btad007-B4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1038\/ng0498-313","article-title":"Predicting functions from protein sequences\u2014where are the bottlenecks?","volume":"18","author":"Bork","year":"1998","journal-title":"Nat. Genet"},{"key":"2023011809302529800_btad007-B5","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":"2023011809302529800_btad007-B6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023011809302529800_btad007-B7","doi-asserted-by":"crossref","first-page":"e1002195","DOI":"10.1371\/journal.pcbi.1002195","article-title":"Accelerated profile HMM searches","volume":"7","author":"Eddy","year":"2011","journal-title":"PLoS Comput. Biol"},{"key":"2023011809302529800_btad007-B8","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":"2023011809302529800_btad007-B9","doi-asserted-by":"crossref","first-page":"1466","DOI":"10.1038\/s41587-019-0333-6","article-title":"Large multiple sequence alignments with a root-to-leaf regressive method","volume":"37","author":"Garriga","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023011809302529800_btad007-B10","author":"Guo","year":"2009"},{"key":"2023011809302529800_btad007-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-021-22869-8","article-title":"CopulaNet: learning residue co-evolution directly from multiple sequence alignment for protein structure prediction","volume":"12","author":"Ju","year":"2021","journal-title":"Nat. Commun"},{"key":"2023011809302529800_btad007-B12","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":"2023011809302529800_btad007-B13","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":"2023011809302529800_btad007-B14","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":"2023011809302529800_btad007-B15","doi-asserted-by":"crossref","first-page":"10557","DOI":"10.1073\/pnas.0409137102","article-title":"An algorithm for progressive multiple alignment of sequences with insertions","volume":"102","author":"L\u00f6ytynoja","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023011809302529800_btad007-B16","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":"2023011809302529800_btad007-B17","first-page":"247","author":"Mirarab","year":"2012"},{"key":"2023011809302529800_btad007-B18","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1089\/cmb.2014.0156","article-title":"PASTA: ultra-large multiple sequence alignment for nucleotide and amino-acid sequences","volume":"22","author":"Mirarab","year":"2015","journal-title":"J. Comput. Biol"},{"key":"2023011809302529800_btad007-B19","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1093\/oxfordjournals.molbev.a025779","article-title":"Effects of nucleotide sequence alignment on phylogeny estimation: a case study of 18S rDNAs of apicomplexa","volume":"14","author":"Morrison","year":"1997","journal-title":"Mol. Biol. Evol"},{"key":"2023011809302529800_btad007-B20","doi-asserted-by":"crossref","first-page":"2933","DOI":"10.1093\/bioinformatics\/btt509","article-title":"Infernal 1.1: 100-fold faster RNA homology searches","volume":"29","author":"Nawrocki","year":"2013","journal-title":"Bioinformatics"},{"key":"2023011809302529800_btad007-B21","doi-asserted-by":"crossref","first-page":"1","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":"2023011809302529800_btad007-B22","doi-asserted-by":"crossref","first-page":"e9490","DOI":"10.1371\/journal.pone.0009490","article-title":"FastTree 2\u2013approximately maximum-likelihood trees for large alignments","volume":"5","author":"Price","year":"2010","journal-title":"PLoS One"},{"key":"2023011809302529800_btad007-B23","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1093\/bioinformatics\/btab788","article-title":"MAGUS+eHMMs: improved multiple sequence alignment accuracy for fragmentary sequences","volume":"38","author":"Shen","year":"2021","journal-title":"Bioinformatics"},{"key":"2023011809302529800_btad007-B24","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1089\/cmb.2021.0585","article-title":"WITCH: improved multiple sequence alignment through weighted consensus HMM alignment","volume":"29","author":"Shen","year":"2022","journal-title":"J. Comput. Biol"},{"key":"2023011809302529800_btad007-B25","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":"2023011809302529800_btad007-B26","doi-asserted-by":"crossref","first-page":"e1008950","DOI":"10.1371\/journal.pcbi.1008950","article-title":"Recursive MAGUS: scalable and accurate multiple sequence alignment","volume":"17","author":"Smirnov","year":"2021","journal-title":"PLoS Comput. Biol"},{"key":"2023011809302529800_btad007-B27","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":"2021","journal-title":"Bioinformatics"},{"key":"2023011809302529800_btad007-B28","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":"2021","journal-title":"Syst. Biol"},{"key":"2023011809302529800_btad007-B29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-019-3019-7","article-title":"HH-suite3 for fast remote homology detection and deep protein annotation","volume":"20","author":"Steinegger","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"2023011809302529800_btad007-B30","doi-asserted-by":"crossref","first-page":"2047","DOI":"10.1093\/bioinformatics\/btl175","article-title":"Bali-Phy: simultaneous Bayesian inference of alignment and phylogeny","volume":"22","author":"Suchard","year":"2006","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad007\/48597904\/btad007.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btad007\/48755283\/btad007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btad007\/48755283\/btad007.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T09:33:33Z","timestamp":1674034413000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad007\/6982552"}},"subtitle":[],"editor":[{"given":"Tobias","family":"Marschall","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad007","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,1,1]]},"published":{"date-parts":[[2023,1,1]]},"article-number":"btad007"}}