{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:52:06Z","timestamp":1740135126111,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,1,13]],"date-time":"2016-01-13T00:00:00Z","timestamp":1452643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2016,1,13]],"date-time":"2016-01-13T00:00:00Z","timestamp":1452643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["05729-2014"],"award-info":[{"award-number":["05729-2014"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["EU H2020-PHC-32-2014 #634650"],"award-info":[{"award-number":["EU H2020-PHC-32-2014 #634650"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-LABX-20"],"award-info":[{"award-number":["ANR-10-LABX-20"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>In recent years, many studies focused on the description and comparison of large sets of related bacteriophage genomes. Due to the peculiar mosaic structure of these genomes, few informative approaches for comparing whole genomes exist: dot plots diagrams give a mostly qualitative assessment of the similarity\/dissimilarity between two or more genomes, and clustering techniques are used to classify genomes. Multiple alignments are conspicuously absent from this scene. Indeed, whole genome aligners interpret lack of similarity between sequences as an indication of rearrangements, insertions, or losses. This behavior makes them ill-prepared to align bacteriophage genomes, where even closely related strains can accomplish the same biological function with highly dissimilar sequences.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>In this paper, we propose a multiple alignment strategy that exploits functional collinearity shared by related strains of bacteriophages, and uses partial orders to capture mosaicism of sets of genomes. As classical alignments do, the computed alignments can be used to predict that genes have the same biological function, even in the absence of detectable similarity. The Alpha aligner implements these ideas in visual interactive displays, and is used to compute several examples of alignments of <jats:italic>Staphylococcus aureus<\/jats:italic> and <jats:italic>Mycobacterium<\/jats:italic> bacteriophages, involving up to 29 genomes. Using these datasets, we prove that Alpha alignments are at least as good as those computed by standard aligners. Comparison with the progressiveMauve aligner \u2013 which implements a partial order strategy, but whose alignments are linearized \u2013 shows a greatly improved interactive graphic display, while avoiding misalignments.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>Multiple alignments of whole bacteriophage genomes work, and will become an important conceptual and visual tool in comparative genomics of sets of related strains.<\/jats:p>\n                <jats:p>A python implementation of Alpha, along with installation instructions for Ubuntu and OSX, is available on bitbucket (<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/bitbucket.org\/thekswenson\/alpha\">https:\/\/bitbucket.org\/thekswenson\/alpha<\/jats:ext-link>).<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-015-0869-5","type":"journal-article","created":{"date-parts":[[2016,1,13]],"date-time":"2016-01-13T03:51:06Z","timestamp":1452657066000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Aligning the unalignable: bacteriophage whole genome alignments"],"prefix":"10.1186","volume":"17","author":[{"given":"S\u00e8verine","family":"B\u00e9rard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Pompidor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Guertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anne","family":"Bergeron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krister M.","family":"Swenson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"issue":"1","key":"869_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jmb.2010.01.011","volume":"397","author":"GF Hatfull","year":"2010","unstructured":"Hatfull GF, Jacobs-Sera D, Lawrence JG, Pope WH, Russell DA, Ko CC, et al. Comparative genomic analysis of 60 Mycobacteriophage genomes: genome clustering, gene acquisition, and gene size. J Mol Biol. 2010; 397(1):119\u201343.","journal-title":"J Mol Biol"},{"key":"869_CR2","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1186\/1471-2164-15-855","volume":"15","author":"JH Grose","year":"2014","unstructured":"Grose JH, Jensen GL, Burnett SH, Breakwell DP. Genomic comparison of 93 Bacillus phages reveals 12 clusters, 14 singletons and remarkable diversity. BMC Genomics. 2014; 15:855.","journal-title":"BMC Genomics"},{"key":"869_CR3","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.virol.2014.08.024","volume":"468\u2013470","author":"JH Grose","year":"2014","unstructured":"Grose JH, Casjens SR. Understanding the enormous diversity of bacteriophages: the tailed phages that infect the bacterial family Enterobacteriaceae. Virology. 2014; 468\u2013470:421\u201343.","journal-title":"Virology"},{"key":"869_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1186\/1471-2105-15-99","volume":"15","author":"B Kehr","year":"2014","unstructured":"Kehr B, Trappe K, Holtgrewe M, Reinert K. Genome alignment with graph data structures: a comparison. BMC Bioinforma. 2014; 15:99.","journal-title":"BMC Bioinforma"},{"key":"869_CR5","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1111\/j.1749-6632.1980.tb27987.x","volume":"354","author":"D Botstein","year":"1980","unstructured":"Botstein D. A theory of modular evolution for bacteriophages. Ann N Y Acad Sci. 1980; 354:484\u201390.","journal-title":"Ann N Y Acad Sci"},{"key":"869_CR6","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.resmic.2008.04.008","volume":"159","author":"GF Hatfull","year":"2008","unstructured":"Hatfull GF, Cresawn SG, Hendrix RW. Comparative genomics of the mycobacteriophages: insights into bacteriophage evolution. Res Microbiol. 2008; 159:332\u20139.","journal-title":"Res Microbiol"},{"issue":"9","key":"869_CR7","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1111\/j.1462-2920.2010.02226.x","volume":"12","author":"J Kahankova","year":"2010","unstructured":"Kahankova J, Pantucek R, Goerke C, Ruzickova V, Holochova P, Doskar J. Multilocus PCR typing strategy for differentiation of Staphylococcus aureus siphoviruses reflecting their modular genome structure. Environ Microbiol. 2010; 12(9):2527\u2013538.","journal-title":"Environ Microbiol"},{"issue":"3","key":"869_CR8","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1128\/MMBR.00014-11","volume":"75","author":"D Veesler","year":"2011","unstructured":"Veesler D, Cambillau C. A common evolutionary origin for tailed-bacteriophage functional modules and bacterial machineries. Microbiol Mol Biol Rev. 2011; 75(3):423\u201333.","journal-title":"Microbiol Mol Biol Rev"},{"issue":"4","key":"869_CR9","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.mib.2005.06.014","volume":"8","author":"SR Casjens","year":"2005","unstructured":"Casjens SR. Comparative genomics and evolution of the tailed-bacteriophages. Curr Opin Microbiol. 2005; 8(4):451\u20138.","journal-title":"Curr Opin Microbiol"},{"key":"869_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/j.mib.2008.09.004","volume":"11","author":"GF Hatfull","year":"2008","unstructured":"Hatfull GF. Bacteriophage genomics. Curr Opin Microbiol. 2008; 11:447\u201353.","journal-title":"Curr Opin Microbiol"},{"key":"869_CR11","volume-title":"The maximum weight trace problem in multiple sequence alignment. CPM\u201993 proceedings, LNCS 684","author":"J Kececioglu","year":"1993","unstructured":"Kececioglu J. The maximum weight trace problem in multiple sequence alignment. CPM\u201993 proceedings, LNCS 684. Berlin: Springer-Verlag; 1993, pp. 106\u2013119."},{"issue":"22","key":"869_CR12","doi-asserted-by":"publisher","first-page":"12098","DOI":"10.1073\/pnas.93.22.12098","volume":"93","author":"B Morgenstern","year":"1996","unstructured":"Morgenstern B, Dress A, Werner T. Multiple DNA and protein sequence alignment based on segment-to-segment comparison. Proc Natl Acad Sci USA. 1996; 93(22):12098\u201312103.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"3","key":"869_CR13","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","volume":"18","author":"C Lee","year":"2002","unstructured":"Lee C, Grasso C, Sharlow MF. Multiple sequence alignment using partial order graphs. Bioinformatics. 2002; 18(3):452\u201364.","journal-title":"Bioinformatics"},{"issue":"6","key":"869_CR14","doi-asserted-by":"publisher","first-page":"11147","DOI":"10.1371\/journal.pone.0011147","volume":"5","author":"AE Darling","year":"2010","unstructured":"Darling AE, Mau B, Perna NT. progressiveMauve: multiple genome alignment with gene gain, loss and rearrangement. PLoS ONE. 2010; 5(6):11147.","journal-title":"PLoS ONE"},{"issue":"3","key":"869_CR15","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1109\/TCBB.2013.68","volume":"10","author":"G Gremme","year":"2013","unstructured":"Gremme G, Steinbiss S, Kurtz S. GenomeTools: a comprehensive software library for efficient processing of structured genome annotations. IEEE\/ACM Trans Comput Biol Bioinform. 2013; 10(3):645\u201356.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"5","key":"869_CR16","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1145\/364099.364331","volume":"7","author":"BA Galler","year":"1964","unstructured":"Galler BA, Fisher MJ. An Improved Equivalence Algorithm. Commun ACM. 1964; 7(5):301\u20133.","journal-title":"Commun ACM"},{"issue":"2","key":"869_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan RE. Efficiency of a Good But Not Linear Set Union Algorithm. J ACM. 1975; 22(2):215\u201325.","journal-title":"J ACM"},{"issue":"11","key":"869_CR18","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1002\/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N","volume":"30","author":"ER Gansner","year":"2000","unstructured":"Gansner ER, North SC. An open graph visualization system and its applications to software engineering. Softw Pract Experience. 2000; 30(11):1203\u20131233.","journal-title":"Softw Pract Experience"},{"key":"869_CR19","doi-asserted-by":"publisher","first-page":"S312","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312","volume":"18(Suppl 1)","author":"M Hohl","year":"2002","unstructured":"Hohl M, Kurtz S, Ohlebusch E. Efficient multiple genome alignment. Bioinformatics. 2002; 18(Suppl 1):S312\u2013S320.","journal-title":"Bioinformatics."},{"key":"869_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1186\/1471-2105-6-171","volume":"6","author":"H Chiapello","year":"2005","unstructured":"Chiapello H, Bourgait I, Sourivong F, Heuclin G, Gendrault-Jacquemard A, Petit MA, et al. Systematic determination of the mosaic structure of bacterial genomes: species backbone versus strain-specific loops. BMC Bioinforma. 2005; 6:171.","journal-title":"BMC Bioinforma"},{"key":"869_CR21","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/msb.2011.75","volume":"7","author":"F Sievers","year":"2011","unstructured":"Sievers F, Wilm A, Dineen D, Gibson TJ, Karplus K, Li W, et al. Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Mol Syst Biol. 2011; 7:539.","journal-title":"Mol Syst Biol"},{"issue":"1","key":"869_CR22","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame C, Higgins DG, Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol. 2000; 302(1):205\u201317.","journal-title":"J Mol Biol"},{"key":"869_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1186\/1471-2105-5-113","volume":"5","author":"RC Edgar","year":"2004","unstructured":"Edgar RC. MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinforma. 2004; 5:113.","journal-title":"BMC Bioinforma"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0869-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-015-0869-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0869-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-015-0869-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:58:12Z","timestamp":1706810292000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-015-0869-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,13]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2016,12]]}},"alternative-id":["869"],"URL":"https:\/\/doi.org\/10.1186\/s12859-015-0869-5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2016,1,13]]},"assertion":[{"value":"6 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"30"}}