{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T07:56:44Z","timestamp":1773388604830,"version":"3.50.1"},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":12,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["5U54HG007990"],"award-info":[{"award-number":["5U54HG007990"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["5T32HG008345-04"],"award-info":[{"award-number":["5T32HG008345-04"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1U01HL137183"],"award-info":[{"award-number":["1U01HL137183"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01HG010053"],"award-info":[{"award-number":["R01HG010053"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["U01HL137183"],"award-info":[{"award-number":["U01HL137183"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["2U41HG007234"],"award-info":[{"award-number":["2U41HG007234"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Graph representations of genomes are capable of expressing more genetic variation and can therefore better represent a population than standard linear genomes. However, due to the greater complexity of genome graphs relative to linear genomes, some functions that are trivial on linear genomes become much more difficult in genome graphs. Calculating distance is one such function that is simple in a linear genome but complicated in a graph context. In read mapping algorithms such distance calculations are fundamental to determining if seed alignments could belong to the same mapping.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We have developed an algorithm for quickly calculating the minimum distance between positions on a sequence graph using a minimum distance index. We have also developed an algorithm that uses the distance index to cluster seeds on a graph. We demonstrate that our implementations of these algorithms are efficient and practical to use for a new generation of mapping algorithms based upon genome graphs.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Our algorithms have been implemented as part of the vg toolkit and are available at https:\/\/github.com\/vgteam\/vg.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa446","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T15:13:59Z","timestamp":1591283639000},"page":"i146-i153","source":"Crossref","is-referenced-by-count":20,"title":["Distance indexing and seed clustering in sequence graphs"],"prefix":"10.1093","volume":"36","author":[{"given":"Xian","family":"Chang","sequence":"first","affiliation":[{"name":"Department of Biomolecular Engineering, University of California Santa Cruz Genomics Institute , Santa Cruz, CA 95060, USA"}]},{"given":"Jordan","family":"Eizenga","sequence":"additional","affiliation":[{"name":"Department of Biomolecular Engineering, University of California Santa Cruz Genomics Institute , Santa Cruz, CA 95060, USA"}]},{"given":"Adam M","family":"Novak","sequence":"additional","affiliation":[{"name":"Department of Biomolecular Engineering, University of California Santa Cruz Genomics Institute , Santa Cruz, CA 95060, USA"}]},{"given":"Jouni","family":"Sir\u00e9n","sequence":"additional","affiliation":[{"name":"Department of Biomolecular Engineering, University of California Santa Cruz Genomics Institute , Santa Cruz, CA 95060, USA"}]},{"given":"Benedict","family":"Paten","sequence":"additional","affiliation":[{"name":"Department of Biomolecular Engineering, University of California Santa Cruz Genomics Institute , Santa Cruz, CA 95060, USA"}]}],"member":"286","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"2024021913325140000_btaa446-B1","first-page":"349","author":"Akiba","year":"2013"},{"key":"2024021913325140000_btaa446-B2","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/978-3-319-22849-5_32","volume-title":"Database and Expert Systems Applications, Lecture Notes in Computer Science","author":"Dave","year":"2015"},{"key":"2024021913325140000_btaa446-B3","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math"},{"key":"2024021913325140000_btaa446-B4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Djidjev","year":"1997"},{"key":"2024021913325140000_btaa446-B5","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1038\/nbt.4227","article-title":"Variation graph toolkit improves read mapping by representing genetic variation in the reference","volume":"36","author":"Garrison","year":"2018","journal-title":"Nat. Biotechnol"},{"key":"2024021913325140000_btaa446-B6","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybernetics"},{"key":"2024021913325140000_btaa446-B7","author":"Jain","year":"2019"},{"key":"2024021913325140000_btaa446-B8","first-page":"219","volume-title":"Geoinformation und Mobilit\u00e4t - von der Forschung zur praktischen Anwendung","author":"Lauther","year":"2004"},{"key":"2024021913325140000_btaa446-B9","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":"2024021913325140000_btaa446-B10","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/11427186_18","volume-title":"Experimental and Efficient Algorithms","author":"M\u00f6hring","year":"2005"},{"key":"2024021913325140000_btaa446-B11","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1101\/gr.214155.116","article-title":"Genome graphs and the evolution of genome inference","volume":"27","author":"Paten","year":"2017","journal-title":"Genome Res"},{"key":"2024021913325140000_btaa446-B12","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1089\/cmb.2017.0251","article-title":"Superbubbles, ultrabubbles, and cacti","volume":"25","author":"Paten","year":"2018","journal-title":"J. Comput. Biol"},{"key":"2024021913325140000_btaa446-B13","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/ICDE.2012.53","article-title":"Approximate shortest distance computing: a query-dependent local landmark scheme","author":"Qiao","year":"2012","journal-title":"2012 IEEE 28th International Conference on Data Engineering"},{"key":"2024021913325140000_btaa446-B14","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1038\/s41588-018-0316-4","article-title":"Fast and accurate genomic analyses using genome graphs","volume":"51","author":"Rakocevic","year":"2019","journal-title":"Nat. Genet"},{"key":"2024021913325140000_btaa446-B15","doi-asserted-by":"crossref","first-page":"3599","DOI":"10.1093\/bioinformatics\/btz162","article-title":"Bit-parallel sequence-to-graph alignment","volume":"35","author":"Rautiainen","year":"2019","journal-title":"Bioinformatics"},{"key":"2024021913325140000_btaa446-B16","doi-asserted-by":"crossref","first-page":"R98","DOI":"10.1186\/gb-2009-10-9-r98","article-title":"Simultaneous alignment of short reads against multiple genomes","volume":"10","author":"Schneeberger","year":"2009","journal-title":"Genome Biol"},{"key":"2024021913325140000_btaa446-B17","first-page":"118","year":"2016"},{"key":"2024021913325140000_btaa446-B18","author":"Vaddadi","year":"2019"},{"key":"2024021913325140000_btaa446-B19","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1038\/nbt.2835","article-title":"Integrating human sequence data sets provides a resource of benchmark SNP and indel genotype calls","volume":"32","author":"Zook","year":"2014","journal-title":"Nat. Biotechnol"},{"key":"2024021913325140000_btaa446-B20","doi-asserted-by":"crossref","first-page":"160025","DOI":"10.1038\/sdata.2016.25","article-title":"Extensive sequencing of seven human genomes to characterize benchmark reference materials","volume":"3","author":"Zook","year":"2016","journal-title":"Scientific Data"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i146\/56702439\/bioinformatics_36_supplement1_i146.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i146\/56702439\/bioinformatics_36_supplement1_i146.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T08:38:42Z","timestamp":1708331922000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_1\/i146\/5870464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":20,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa446","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2019.12.20.884924","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":[[2020,7]]},"published":{"date-parts":[[2020,7,1]]}}}