{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:56Z","timestamp":1772138096230,"version":"3.50.1"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Whole-genome alignment (WGA) methods show insufficient scalability toward the generation of large-scale WGAs. Profile alignment-based approaches revolutionized the fields of multiple sequence alignment construction methods by significantly reducing computational complexity and runtime. However, WGAs need to consider genomic rearrangements between genomes, which make the profile-based extension of several whole-genomes challenging. Currently, none of the available methods offer the possibility to align or extend WGA profiles.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>Here, we present genome profile alignment, an approach that aligns the profiles of WGAs and that is capable of producing large-scale WGAs many times faster than conventional methods. Our concept relies on already available whole-genome aligners, which are used to compute several smaller sets of aligned genomes that are combined to a full WGA with a divide and conquer approach. To align or extend WGA profiles, we make use of the SuperGenome data structure, which features a bidirectional mapping between individual sequence and alignment coordinates. This data structure is used to efficiently transfer different coordinate systems into a common one based on the principles of profiles alignments. The approach allows the computation of a WGA where alignments are subsequently merged along a guide tree. The current implementation uses progressiveMauve and offers the possibility for parallel computation of independent genome alignments. Our results based on various bacterial datasets up to several hundred genomes show that we can reduce the runtime from months to hours with a quality that is negligibly worse than the WGA computed with the conventional progressiveMauve tool.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>GPA is freely available at https:\/\/lambda.informatik.uni-tuebingen.de\/gitlab\/ahennig\/GPA. GPA is implemented in Java, uses progressiveMauve and offers a parallel computation of WGAs.<\/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\/btz377","type":"journal-article","created":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T07:20:03Z","timestamp":1557386403000},"page":"i71-i80","source":"Crossref","is-referenced-by-count":2,"title":["Efficient merging of genome profile alignments"],"prefix":"10.1093","volume":"35","author":[{"given":"Andr\u00e9","family":"Hennig","sequence":"first","affiliation":[{"name":"Center for Bioinformatics (ZBIT), Integrative Transcriptomics, Eberhard Karls University of T\u00fcbingen, T\u00fcbingen, Germany"}]},{"given":"Kay","family":"Nieselt","sequence":"additional","affiliation":[{"name":"Center for Bioinformatics (ZBIT), Integrative Transcriptomics, Eberhard Karls University of T\u00fcbingen, T\u00fcbingen, Germany"}]}],"member":"286","published-online":{"date-parts":[[2019,7,5]]},"reference":[{"key":"2023062712410978100_btz377-B1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.meegid.2018.01.014","article-title":"Evaluating the use of whole-genome sequencing for outbreak investigations in the lack of closely related reference genome","volume":"59","author":"Abdelbary","year":"2018","journal-title":"Infect. Genet. Evol"},{"key":"2023062712410978100_btz377-B2","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1093\/bioinformatics\/btq665","article-title":"Mugsy: fast multiple alignment of closely related whole genomes","volume":"27","author":"Angiuoli","year":"2011","journal-title":"Bioinformatics"},{"key":"2023062712410978100_btz377-B3","doi-asserted-by":"crossref","first-page":"272.","DOI":"10.1186\/1471-2105-12-272","article-title":"Improving pan-genome annotation using whole genome multiple alignment","volume":"12","author":"Angiuoli","year":"2011","journal-title":"BMC Bioinf"},{"key":"2023062712410978100_btz377-B4","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":"2023062712410978100_btz377-B5","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1016\/S0140-6736(13)60632-7","article-title":"Whole-genome sequencing to identify transmission of Mycobacterium abscessus between patients with cystic fibrosis: a retrospective cohort study","volume":"381","author":"Bryant","year":"2013","journal-title":"Lancet"},{"key":"2023062712410978100_btz377-B6","doi-asserted-by":"crossref","first-page":"3.","DOI":"10.1186\/1745-6150-8-3","article-title":"Next-generation phylogenomics","volume":"8","author":"Chan","year":"2013","journal-title":"Biol. Direct"},{"key":"2023062712410978100_btz377-B7","doi-asserted-by":"crossref","first-page":"e11147.","DOI":"10.1371\/journal.pone.0011147","article-title":"progressiveMauve: multiple genome alignment with gene gain, loss and rearrangement","volume":"5","author":"Darling","year":"2010","journal-title":"PLoS One"},{"key":"2023062712410978100_btz377-B8","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1101\/gr.2289704","article-title":"Mauve: multiple alignment of conserved genomic sequence with rearrangements","volume":"14","author":"Darling","year":"2004","journal-title":"Genome Res"},{"key":"2023062712410978100_btz377-B9","doi-asserted-by":"crossref","first-page":"2077","DOI":"10.1101\/gr.174920.114","article-title":"Alignathon: a competitive assessment of whole-genome alignment methods","volume":"24","author":"Earl","year":"2014","journal-title":"Genome Res"},{"key":"2023062712410978100_btz377-B10","author":"Edgar","year":"2009"},{"key":"2023062712410978100_btz377-B11","author":"Edgar","year":"2012"},{"key":"2023062712410978100_btz377-B12","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1016\/j.ijmm.2017.11.011","article-title":"Aureowiki\u2014the repository of the Staphylococcus aureus research and annotation community","volume":"308","author":"Fuchs","year":"2017","journal-title":"Int. J. Med. Microbiol"},{"key":"2023062712410978100_btz377-B13","doi-asserted-by":"crossref","first-page":"15.","DOI":"10.1186\/s13015-018-0133-4","article-title":"Coordinate systems for supergenomes","volume":"13","author":"G\u00e4rtner","year":"2018","journal-title":"Algorithms Mol. Biol"},{"key":"2023062712410978100_btz377-B14","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF02462264","article-title":"Consistency of optimal sequence alignments","volume":"52","author":"Gotoh","year":"1990","journal-title":"Bull. Math. Biol"},{"key":"2023062712410978100_btz377-B15","doi-asserted-by":"crossref","first-page":"S3.","DOI":"10.1186\/1471-2105-16-S11-S3","article-title":"Pan-tetris: an interactive visualisation for pan-genomes","volume":"16","author":"Hennig","year":"2015","journal-title":"BMC Bioinf"},{"key":"2023062712410978100_btz377-B16","doi-asserted-by":"crossref","first-page":"i7","DOI":"10.1093\/bioinformatics\/bts217","article-title":"GenomeRing: alignment visualization based on SuperGenome coordinates","volume":"28","author":"Herbig","year":"2012","journal-title":"Bioinformatics"},{"key":"2023062712410978100_btz377-B17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02257378","article-title":"The alignment of sets of sequences and the construction of phyletic trees: an integrated method","volume":"20","author":"Hogeweg","year":"1984","journal-title":"J. Mol. Evol"},{"key":"2023062712410978100_btz377-B18","doi-asserted-by":"crossref","first-page":"47.","DOI":"10.1186\/s12864-017-4401-3","article-title":"seq-seq-pan: building a computational pan-genome data structure on whole genome alignment","volume":"19","author":"Jandrasits","year":"2018","journal-title":"BMC Genomics"},{"key":"2023062712410978100_btz377-B19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-1-62703-646-7_15","article-title":"Large-scale multiple sequence alignment and tree estimation using SAT\u00e9","volume":"1079","author":"Liu","year":"2014","journal-title":"Methods Mol. Biol."},{"key":"2023062712410978100_btz377-B20","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.gde.2005.09.006","article-title":"The microbial pan-genome","volume":"15","author":"Medini","year":"2005","journal-title":"Curr. Opin. Genet. Dev"},{"key":"2023062712410978100_btz377-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 alignment1","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol"},{"key":"2023062712410978100_btz377-B22","doi-asserted-by":"crossref","first-page":"20380.","DOI":"10.2807\/ese.18.04.20380-en","article-title":"Overview of molecular typing methods for outbreak detection and epidemiological surveillance","volume":"18","author":"Sabat","year":"2013","journal-title":"Eurosurveillance"},{"key":"2023062712410978100_btz377-B23","first-page":"506.","article-title":"Whole genome de novo assemblies of three divergent strains of rice, Oryza sativa, document novel gene space of aus and indica","volume":"15","author":"Schatz","year":"2014","journal-title":"Genome Biol"},{"key":"2023062712410978100_btz377-B24","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"Balibase 3.0: latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins"},{"key":"2023062712410978100_btz377-B25","doi-asserted-by":"crossref","first-page":"524.","DOI":"10.1186\/s13059-014-0524-x","article-title":"The harvest suite for rapid core-genome alignment and visualization of thousands of intraspecific microbial genomes","volume":"15","author":"Treangen","year":"2014","journal-title":"Genome Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i71\/50721523\/bioinformatics_35_14_i71.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i71\/50721523\/bioinformatics_35_14_i71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T08:41:50Z","timestamp":1687855310000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/14\/i71\/5529231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":25,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2019,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz377","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/309047","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":[[2019,7]]},"published":{"date-parts":[[2019,7]]}}}