{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:07:12Z","timestamp":1744157232290,"version":"3.37.3"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2018,9,9]],"date-time":"2018-09-09T00:00:00Z","timestamp":1536451200000},"content-version":"vor","delay-in-days":8,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100013886","name":"BE Basic Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013886","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Dutch Ministry of Economic Affairs"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>A long-standing limitation in comparative genomic studies is the dependency on a reference genome, which hinders the spectrum of genetic diversity that can be identified across a population of organisms. This is especially true in the microbial world where genome architectures can significantly vary. There is therefore a need for computational methods that can simultaneously analyze the architectures of multiple genomes without introducing bias from a reference.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this article, we present Ptolemy: a novel method for studying the diversity of genome architectures\u2014such as structural variation and pan-genomes\u2014across a collection of microbial assemblies without the need of a reference. Ptolemy is a \u2018top-down\u2019 approach to compare whole genome assemblies. Genomes are represented as labeled multi-directed graphs\u2014known as quivers\u2014which are then merged into a single, canonical quiver by identifying \u2018gene anchors\u2019 via synteny analysis. The canonical quiver represents an approximate, structural alignment of all genomes in a given collection encoding structural variation across (sub-) populations within the collection. We highlight various applications of Ptolemy by analyzing structural variation and the pan-genomes of different datasets composing of Mycobacterium, Saccharomyces, Escherichia and Shigella species. Our results show that Ptolemy is flexible and can handle both conserved and highly dynamic genome architectures. Ptolemy is user-friendly\u2014requires only FASTA-formatted assembly along with a corresponding GFF-formatted file\u2014and resource-friendly\u2014can align 24 genomes in \u223c10 mins with four CPUs and &amp;lt;2 GB of RAM.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Github: https:\/\/github.com\/AbeelLab\/ptolemy<\/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\/bty614","type":"journal-article","created":{"date-parts":[[2018,7,19]],"date-time":"2018-07-19T22:46:32Z","timestamp":1532040392000},"page":"i732-i742","source":"Crossref","is-referenced-by-count":6,"title":["Approximate, simultaneous comparison of microbial genome architectures via syntenic anchoring of quiver representations"],"prefix":"10.1093","volume":"34","author":[{"given":"Alex N","family":"Salazar","sequence":"first","affiliation":[{"name":"Delft Bioinformatics Lab, Delft University of Technology, Delft, The Netherlands"},{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Abeel","sequence":"additional","affiliation":[{"name":"Delft Bioinformatics Lab, Delft University of Technology, Delft, The Netherlands"},{"name":"Infectious Disease and Microbiome Program, Broad Institute of MIT and Harvard, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,9,8]]},"reference":[{"key":"2023061313480507600_bty614-B1","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":"2023061313480507600_bty614-B2","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1046\/j.1365-2958.2000.02179.x","article-title":"The virulence plasmid pWR100 and the repertoire of proteins secreted by the type III secretion apparatus of Shigella flexneri","volume":"38","author":"Buchrieser","year":"2000","journal-title":"Mol. Microbiol."},{"key":"2023061313480507600_bty614-B3","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1128\/CMR.00013-07","article-title":"Type III secretion systems and disease","volume":"20","author":"Coburn","year":"2007","journal-title":"Clin. Microbiol. Rev."},{"key":"2023061313480507600_bty614-B4","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1038\/31159","article-title":"Deciphering the biology of Mycobacterium tuberculosis from the complete genome sequence","volume":"393","author":"Cole","year":"1998","journal-title":"Nature"},{"key":"2023061313480507600_bty614-B5","doi-asserted-by":"crossref","DOI":"10.1038\/ncomms5812","article-title":"A robust SNP barcode for typing Mycobacterium tuberculosis complex strains","volume":"5","author":"Coll","year":"2014","journal-title":"Nat. Commun"},{"key":"2023061313480507600_bty614-B6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/j.smim.2014.09.012","article-title":"Consequences of genomic diversity in Mycobacterium tuberculosis","volume":"26","author":"Coscolla","year":"2014","journal-title":"Semin. Immunol."},{"key":"2023061313480507600_bty614-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":"2023061313480507600_bty614-B8","first-page":"200","article-title":"Quiver representations","volume":"52","author":"Derksen","year":"2005","journal-title":"Not. AMS"},{"key":"2023061313480507600_bty614-B9","doi-asserted-by":"crossref","first-page":"e92621","DOI":"10.1371\/journal.pone.0092621","article-title":"SynChro: a fast and easy tool to reconstruct and visualize synteny blocks along eukaryotic chromosomes","volume":"9","author":"Drillon","year":"2014","journal-title":"PLoS One"},{"key":"2023061313480507600_bty614-B10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-1-59745-427-8_3","article-title":"Genetic maps and the use of synteny","volume":"513","author":"Duran","year":"2009","journal-title":"Methods Mol. Biol."},{"key":"2023061313480507600_bty614-B11","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1017\/S0956796801004075","article-title":"Inductive graphs and functional graph algorithms","volume":"11","author":"Erwig","year":"2001","journal-title":"J. Funct. Prog."},{"key":"2023061313480507600_bty614-B12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","article-title":"Homology a personal view on some of the problems","volume":"16","author":"Fitch","year":"2000","journal-title":"Trends Genet."},{"key":"2023061313480507600_bty614-B13","first-page":"1","article-title":"Sequence variation aware genome references and read mapping with the variation graph toolkit","volume":"234856","author":"Garrison","year":"2017","journal-title":"bioRxiv"},{"key":"2023061313480507600_bty614-B14","doi-asserted-by":"crossref","first-page":"3437","DOI":"10.1093\/bioinformatics\/btv389","article-title":"Proteny: discovering and visualizing statistically significant syntenic clusters at the proteome level","volume":"31","author":"Gehrmann","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061313480507600_bty614-B15","doi-asserted-by":"crossref","first-page":"i9","DOI":"10.1093\/bioinformatics\/btu259","article-title":"Evaluating synteny for improved comparative studies","volume":"30","author":"Ghiurcuta","year":"2014","journal-title":"Bioinformatics"},{"key":"2023061313480507600_bty614-B16","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1038\/nbt.4060","article-title":"Nanopore sequencing and assembly of a human genome with ultra-long reads","volume":"36","author":"Jain","year":"2018","journal-title":"Nat. Biotechnol"},{"key":"2023061313480507600_bty614-B17","doi-asserted-by":"crossref","first-page":"168","DOI":"10.4056\/sigs.2084864","article-title":"Solving the problem: genome annotation standards before the data deluge","volume":"5","author":"Klimke","year":"2011","journal-title":"Stand. Genomic Sci."},{"key":"2023061313480507600_bty614-B18","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol."},{"key":"2023061313480507600_bty614-B19","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/j.tig.2008.08.009","article-title":"The quest for orthologs: finding the corresponding gene across genomes","volume":"24","author":"Kuzniar","year":"2008","journal-title":"Trends Genet."},{"key":"2023061313480507600_bty614-B20","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023061313480507600_bty614-B21","doi-asserted-by":"crossref","first-page":"e7778","DOI":"10.1371\/journal.pone.0007778","article-title":"Genome analysis of multi- and extensively-drug-resistant tuberculosis from KwaZulu-Natal, South Africa","volume":"4","author":"Ioerger","year":"2009","journal-title":"PLoS One"},{"key":"2023061313480507600_bty614-B22","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1038\/nmeth.3444","article-title":"A complete bacterial genome assembled de novo using only nanopore sequencing data","volume":"12","author":"Loman","year":"2015","journal-title":"Nat. Methods"},{"key":"2023061313480507600_bty614-B23","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1007\/s00248-010-9717-3","article-title":"Comparison of 61 sequenced Escherichia coli genomes","volume":"60","author":"Lukjancenko","year":"2010","journal-title":"Microb. Ecol."},{"key":"2023061313480507600_bty614-B24","first-page":"118","article-title":"Computational pan-genomics: status, promises and challenges","volume":"19","author":"Marschall","year":"2018","journal-title":"Brief. Bioinform."},{"key":"2023061313480507600_bty614-B25","doi-asserted-by":"crossref","first-page":"e30593","DOI":"10.1371\/journal.pone.0030593","article-title":"Comparative analysis of Mycobacterium tuberculosis pe and ppe genes reveals high sequence variation and an apparent absence of selective constraints","volume":"7","author":"McEvoy","year":"2012","journal-title":"PLoS One"},{"key":"2023061313480507600_bty614-B26","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1534\/g3.116.029389","article-title":"Genome sequence and analysis of a stress-tolerant, wild-derived strain of Saccharomyces cerevisiae used in biofuels research","volume":"6","author":"McIlwain","year":"2016","journal-title":"G3 (Betheseda)"},{"key":"2023061313480507600_bty614-B27","first-page":"215","article-title":"Sibelia: a scalable and comprehensive synteny block generation tool for closely related microbial genomes","volume-title":"Algorithms in Bioinformatics Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)","author":"Minkin","year":"2013"},{"key":"2023061313480507600_bty614-B28","doi-asserted-by":"crossref","DOI":"10.1186\/s13059-016-0997-x","article-title":"Mash: fast genome and metagenome distance estimation using MinHash","volume":"17","author":"Ondov","year":"2016","journal-title":"Genome Biol."},{"key":"2023061313480507600_bty614-B29","doi-asserted-by":"crossref","first-page":"1512","DOI":"10.1101\/gr.123356.111","article-title":"Cactus: algorithms for genome multiple sequence alignment","volume":"21","author":"Paten","year":"2011","journal-title":"Genome Res."},{"key":"2023061313480507600_bty614-B30","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":"2023061313480507600_bty614-B31","doi-asserted-by":"crossref","first-page":"2509","DOI":"10.1093\/bioinformatics\/btq465","article-title":"DRIMM-Synteny: decomposing genomes into evolutionary conserved segments","volume":"26","author":"Pham","year":"2010","journal-title":"Bioinformatics"},{"key":"2023061313480507600_bty614-B32","doi-asserted-by":"crossref","first-page":"1909","DOI":"10.1099\/mic.0.033811-0","article-title":"Using comparative genome analysis to identify problems in annotated microbial genomes","volume":"156","author":"Poptsova","year":"2010","journal-title":"Microbiology"},{"key":"2023061313480507600_bty614-B33","doi-asserted-by":"crossref","first-page":"R233","DOI":"10.1186\/gb-2007-8-11-r233","article-title":"The determinants of gene order conservation in yeasts","volume":"8","author":"Poyatos","year":"2007","journal-title":"Genome Biol."},{"key":"2023061313480507600_bty614-B34","doi-asserted-by":"crossref","first-page":"e11","DOI":"10.1093\/nar\/gkr955","article-title":"i-ADHoRe 3.0-fast and sensitive detection of genomic homology in extremely large data sets","volume":"40","author":"Proost","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023061313480507600_bty614-B35","article-title":"Fast and accurate genomic analyses using genome graphs","volume":"194530","author":"Rakocevic","year":"2017","journal-title":"bioRxiv"},{"key":"2023061313480507600_bty614-B36","doi-asserted-by":"crossref","first-page":"e00371","DOI":"10.1128\/genomeA.00371-15","article-title":"Complete genome sequence of the clinical Beijing-like strain Mycobacterium tuberculosis 323 using the pacbio real-time sequencing platform","volume":"3","author":"Rodr\u00edguez","year":"2015","journal-title":"Genome Announc."},{"key":"2023061313480507600_bty614-B37","doi-asserted-by":"crossref","first-page":"12567","DOI":"10.1038\/srep12567","article-title":"Analysis of IS6110 insertion sites provide a glimpse into genome evolution of Mycobacterium tuberculosis","volume":"5","author":"Roychowdhury","year":"2015","journal-title":"Sci. Rep."},{"key":"2023061313480507600_bty614-B38","doi-asserted-by":"crossref","first-page":"fox074","DOI":"10.1093\/femsyr\/fox074","article-title":"Nanopore sequencing enables near-complete de novo assembly of Saccharomyces cerevisiae reference strain CEN.PK113-7D","volume":"17","author":"Salazar","year":"2017","journal-title":"FEMS Yeast Res."},{"key":"2023061313480507600_bty614-B39","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/B0-12-512666-2\/00418-1","article-title":"Finite-dimensional algebras and quivers","volume-title":"Encyclopedia of Mathematical Physics","author":"Savage","year":"2006"},{"key":"2023061313480507600_bty614-B40","doi-asserted-by":"crossref","first-page":"3286","DOI":"10.1093\/gbe\/evv219","article-title":"SynFind: compiling syntenic regions across any set of genomes on demand","volume":"7","author":"Tang","year":"2015","journal-title":"Genome. Biol. Evol."},{"key":"2023061313480507600_bty614-B41","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1126\/science.1153917","article-title":"Synteny and collinearity in plant genomes","volume":"320","author":"Tang","year":"2008","journal-title":"Science"},{"key":"2023061313480507600_bty614-B42","doi-asserted-by":"crossref","first-page":"4865","DOI":"10.1073\/pnas.0305634101","article-title":"Functional and evolutionary genomics of Mycobacterium tuberculosis: insights from genomic deletions in 100 strains","volume":"101","author":"Tsolaki","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023061313480507600_bty614-B43","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1101\/gr.221184.117","article-title":"MinION-based long-read sequencing and assembly extends the Caenorhabditis elegans reference genome","volume":"28","author":"Tyson","year":"2018","journal-title":"Genome Res."},{"key":"2023061313480507600_bty614-B44","article-title":"Panaconda: application of pan-synteny graph models to genome content analysis","volume":"215988","author":"Warren","year":"2017","journal-title":"doi.org"},{"key":"2023061313480507600_bty614-B45","doi-asserted-by":"crossref","first-page":"3350","DOI":"10.1093\/bioinformatics\/btv383","article-title":"Bandage: interactive visualization of de novo genome assemblies","volume":"31","author":"Wick","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061313480507600_bty614-B46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-0-387-98141-3","volume-title":"ggplot2: Elegant Graphic for Data Analysis","author":"Wickham","year":"2009"},{"key":"2023061313480507600_bty614-B47","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1038\/ng.3847","article-title":"Contrasting evolutionary genome dynamics between domesticated and wild yeasts","volume":"49","author":"Yue","year":"2017","journal-title":"Nat. Genet."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i732\/50581862\/bioinformatics_34_17_i732.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i732\/50581862\/bioinformatics_34_17_i732.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T13:48:57Z","timestamp":1686664137000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/17\/i732\/5093246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,1]]},"references-count":47,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2018,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty614","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2018,9,1]]},"published":{"date-parts":[[2018,9,1]]}}}