{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:18:30Z","timestamp":1764688710553},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2859,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Multiple sequence alignment is a cornerstone of comparative genomics. Much work has been done to improve methods for this task, particularly for the alignment of small sequences, and especially for amino acid sequences. However, less work has been done in making promising methods that work on the small-scale practically for the alignment of much larger genomic sequences.<\/jats:p>\n               <jats:p>Results: We take the method of probabilistic consistency alignment and make it practical for the alignment of large genomic sequences. In so doing we develop a set of new technical methods, combined in a framework we term \u2018sequence progressive alignment\u2019, because it allows us to iteratively compute an alignment by passing over the input sequences from left to right. The result is that we massively decrease the memory consumption of the program relative to a naive implementation. The general engineering of the challenges faced in scaling such a computationally intensive process offer valuable lessons for planning related large-scale sequence analysis algorithms. We also further show the strong performance of Pecan using an extended analysis of ancient repeat alignments. Pecan is now one of the default alignment programs that has and is being used by a number of whole-genome comparative genomic projects.<\/jats:p>\n               <jats:p>Availability: The Pecan program is freely available at http:\/\/www.ebi.ac.uk\/\u223cbjp\/pecan\/ Pecan whole genome alignments can be found in the Ensembl genome browser.<\/jats:p>\n               <jats:p>Contact: \u00a0benedict@soe.ucsc.edu<\/jats:p>\n               <jats:p>supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn630","type":"journal-article","created":{"date-parts":[[2008,12,5]],"date-time":"2008-12-05T01:25:18Z","timestamp":1228440318000},"page":"295-301","source":"Crossref","is-referenced-by-count":45,"title":["Sequence progressive alignment, a framework for practical large-scale probabilistic consistency alignment"],"prefix":"10.1093","volume":"25","author":[{"given":"Benedict","family":"Paten","sequence":"first","affiliation":[{"name":"1 Department of Engineering, University of California, Santa Cruz CA, USA and 2EMBL European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Herrero","sequence":"additional","affiliation":[{"name":"1 Department of Engineering, University of California, Santa Cruz CA, USA and 2EMBL European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathryn","family":"Beal","sequence":"additional","affiliation":[{"name":"1 Department of Engineering, University of California, Santa Cruz CA, USA and 2EMBL European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewan","family":"Birney","sequence":"additional","affiliation":[{"name":"1 Department of Engineering, University of California, Santa Cruz CA, USA and 2EMBL European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge, CB10 1SD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,12,4]]},"reference":[{"key":"2023013110012861700_B1","first-page":"1","article-title":"An equality and associated maximisation technique in statistical estimation for probabilistic functions of Markov processes","volume":"3","author":"Baum","year":"1972","journal-title":"Inequalities"},{"key":"2023013110012861700_B2","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1101\/gr.1933104","article-title":"Aligning multiple genomic sequences with the threaded blockset aligner","volume":"14","author":"Blanchette","year":"2004","journal-title":"Genome Res."},{"key":"2023013110012861700_B3","doi-asserted-by":"crossref","first-page":"3258","DOI":"10.1093\/bioinformatics\/btm402","article-title":"Transducers: an emerging probabilistic framework for modeling indels on trees","volume":"23","author":"Bradley","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013110012861700_B4","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1101\/gr.1960404","article-title":"MAVID: constrained ancestral alignment of multiple sequences","volume":"14","author":"Bray","year":"2004","journal-title":"Genome Res."},{"key":"2023013110012861700_B5","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1101\/gr.926603","article-title":"LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA","volume":"13","author":"Brudno","year":"2003","journal-title":"Genome Res."},{"key":"2023013110012861700_B6","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/S0092-8240(05)80237-X","article-title":"Constrained sequence alignment","volume":"55","author":"Chao","year":"1993","journal-title":"Bull. Math. Biol."},{"key":"2023013110012861700_B7","volume-title":"Introduction to Algorithms.","author":"Cormen","year":"2001"},{"key":"2023013110012861700_B8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/978-1-59745-514-5_14","article-title":"Aligning multiple whole genomes with mercator and mavid","volume":"395","author":"Dewey","year":"2007","journal-title":"Methods Mol. Biol."},{"key":"2023013110012861700_B9","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"Probcons: Probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res."},{"key":"2023013110012861700_B10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis.","author":"Durbin","year":"1998"},{"key":"2023013110012861700_B11","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1089\/cmb.2006.13.1323","article-title":"Settling the intractability of multiple alignment","volume":"13","author":"Elias","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023013110012861700_B12","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","article-title":"Progressive sequence alignment as a prerequisite to correct phylogenetic trees","volume":"25","author":"Feng D.F.","year":"1987","journal-title":"J. Mol. Evol."},{"key":"2023013110012861700_B13","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gkm988","article-title":"Ensembl 2008","author":"Flicek","year":"2007","journal-title":"Nucleic Acids Res"},{"key":"2023013110012861700_B14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences.","author":"Gusfield","year":"1997"},{"key":"2023013110012861700_B15","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1089\/cmb.1998.5.493","article-title":"Dynamic programming alignment accuracy","volume":"5","author":"Holmes","year":"1998","journal-title":"J. Comput. Biol."},{"key":"2023013110012861700_B16","first-page":"106","article-title":"The maximum weight trace problem in multiple sequence alignment","volume":"684","author":"Kececioglu","year":"1993","journal-title":"LNCS"},{"key":"2023013110012861700_B17","doi-asserted-by":"crossref","first-page":"1632","DOI":"10.1126\/science.1158395","article-title":"Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis","volume":"320","author":"L\u00f6ytynoja","year":"2008","journal-title":"Science"},{"key":"2023013110012861700_B18","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1101\/gr.6034307","article-title":"Analyses of deep mammalian sequence alignments and constraint predictions for 1% of the human genome","volume":"17","author":"Margulies","year":"2007","journal-title":"Genome Res."},{"key":"2023013110012861700_B19","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1089\/cmb.1996.3.563","article-title":"Progressive multiple alignment with constraints","volume":"3","author":"Myers","year":"1996","journal-title":"J. Comput. Biol."},{"key":"2023013110012861700_B20","doi-asserted-by":"crossref","first-page":"e123","DOI":"10.1371\/journal.pcbi.0030123","article-title":"Recent evolutions of multiple sequence alignment algorithms","volume":"3","author":"Notredame","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023013110012861700_B21","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-Coffee: a novel method for fast and accurate multiple sequence alignment","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023013110012861700_B22","doi-asserted-by":"crossref","first-page":"1814","DOI":"10.1101\/gr.076554.108","article-title":"Enredo and pecan: Genome-wide mammalian consistency-based multiple alignment with paralogs","volume":"18","author":"Paten","year":"2008","journal-title":"Genome Res."},{"key":"2023013110012861700_B23","doi-asserted-by":"crossref","first-page":"1829","DOI":"10.1101\/gr.076521.108","article-title":"Genome-wide nucleotide-level mammalian ancestor reconstruction","volume":"18","author":"Paten","year":"2008","journal-title":"Genome Res."},{"key":"2023013110012861700_B24","doi-asserted-by":"crossref","first-page":"i187","DOI":"10.1093\/bioinformatics\/btn281","article-title":"Segment-based multiple sequence alignment","volume":"24","author":"Rausch","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013110012861700_B25","doi-asserted-by":"crossref","first-page":"e24","DOI":"10.1093\/bioinformatics\/btl311","article-title":"Multiple alignment by sequence annealing","volume":"23","author":"Schwartz","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013110012861700_B26","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1101\/gr.809403","article-title":"Human-mouse alignments with BLASTZ","volume":"13","author":"Schwartz","year":"2003","journal-title":"Genome Res."},{"key":"2023013110012861700_B27","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1186\/1471-2105-6-31","article-title":"Automated generation of heuristics for biological sequence comparison","volume":"6","author":"Slater","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023013110012861700_B28","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/3\/295\/48983379\/bioinformatics_25_3_295.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/3\/295\/48983379\/bioinformatics_25_3_295.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T18:45:18Z","timestamp":1675190718000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/3\/295\/243970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,4]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn630","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,2,1]]},"published":{"date-parts":[[2008,12,4]]}}}