{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:45:24Z","timestamp":1740185124533,"version":"3.37.3"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Gordon and Betty Moore Foundation\u2019s Data-Driven Discovery Initiative","award":["GBMF4554"],"award-info":[{"award-number":["GBMF4554"]}]},{"DOI":"10.13039\/100000002","name":"US National Institutes of Health","doi-asserted-by":"crossref","award":["R01GM122935"],"award-info":[{"award-number":["R01GM122935"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["DBI-1937540"],"award-info":[{"award-number":["DBI-1937540"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Carnegie Mellon University School of Computer Science Sansom"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Intra-sample heterogeneity describes the phenomenon where a genomic sample contains a diverse set of genomic sequences. In practice, the true string sets in a sample are often unknown due to limitations in sequencing technology. In order to compare heterogeneous samples, genome graphs can be used to represent such sets of strings. However, a genome graph is generally able to represent a string set universe that contains multiple sets of strings in addition to the true string set. This difference between genome graphs and string sets is not well characterized. As a result, a distance metric between genome graphs may not match the distance between true string sets.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We extend a genome graph distance metric, Graph Traversal Edit Distance (GTED) proposed by Ebrahimpour Boroojeny et al., to FGTED to model the distance between heterogeneous string sets and show that GTED and FGTED always underestimate the Earth Mover\u2019s Edit Distance (EMED) between string sets. We introduce the notion of string set universe diameter of a genome graph. Using the diameter, we are able to upper-bound the deviation of FGTED from EMED and to improve FGTED so that it reduces the average error in empirically estimating the similarity between true string sets. On simulated T-cell receptor sequences and actual Hepatitis B virus genomes, we show that the diameter-corrected FGTED reduces the average deviation of the estimated distance from the true string set distances by more than 250%.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>Data and source code for reproducing the experiments are available at: https:\/\/github.com\/Kingsford-Group\/gtedemedtest\/.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac264","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i404-i412","source":"Crossref","is-referenced-by-count":1,"title":["The effect of genome graph expressiveness on the discrepancy between genome graph distance and string set distance"],"prefix":"10.1093","volume":"38","author":[{"given":"Yutong","family":"Qiu","sequence":"first","affiliation":[{"name":"Computational Biology Department, Carnegie Mellon University , Pittsburgh, PA 15232, USA"}]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[{"name":"Computational Biology Department, Carnegie Mellon University , Pittsburgh, PA 15232, USA"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"i169","DOI":"10.1093\/bioinformatics\/bty292","article-title":"A space and time-efficient index for the compacted colored de Bruijn graph","volume":"34","author":"Almodaresi","year":"2018","journal-title":"Bioinformatics"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1186\/s12859-017-1556-5","article-title":"The repertoire dissimilarity index as a method to compare lymphocyte receptor repertoires","volume":"18","author":"Bolen","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1038\/ng.3257","article-title":"Improved genome inference in the MHC using a population reference graph","volume":"47","author":"Dilthey","year":"2015","journal-title":"Nat. Genet"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1089\/cmb.2019.0511","article-title":"Graph traversal edit distance and extensions","volume":"27","author":"Ebrahimpour Boroojeny","year":"2020","journal-title":"J. Comput. Biol"},{"key":"2023041407555222500_","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":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"D482","DOI":"10.1093\/nar\/gkw1065","article-title":"Virus variation resource\u2014improved response to emergent viral outbreaks","volume":"45","author":"Hatcher","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-020-02135-8","article-title":"Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs","volume":"21","author":"Holley","year":"2020","journal-title":"Genome Biol"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1089\/cmb.2019.0066","article-title":"On the complexity of sequence-to-graph alignment","volume":"27","author":"Jain","year":"2020","journal-title":"J. Comput. Biol"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1471-2105-11-21","article-title":"Assembly complexity of prokaryotic genomes using short reads","volume":"11","author":"Kingsford","year":"2010","journal-title":"BMC Bioinformatics"},{"first-page":"957","year":"2015","author":"Kusner","key":"2023041407555222500_"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1093\/bioinformatics\/18.3.452","article-title":"Multiple sequence alignment using partial order graphs","volume":"18","author":"Lee","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1186\/s13059-018-1388-2","article-title":"Kourami: graph-guided assembly for novel human leukocyte antigen allele discovery","volume":"19","author":"Lee","year":"2018","journal-title":"Genome Biol"},{"volume-title":"The Immunoglobulin Factsbook","year":"2001","author":"Lefranc","key":"2023041407555222500_"},{"first-page":"707","year":"1966","author":"Levenshtein","key":"2023041407555222500_"},{"first-page":"251","year":"2001","author":"Levina","key":"2023041407555222500_"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-020-02168-z","article-title":"The design and construction of reference pangenome graphs with minigraph","volume":"21","author":"Li","year":"2020","journal-title":"Genome Biol"},{"first-page":"68","year":"2016","author":"Mangul","key":"2023041407555222500_"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"101224","DOI":"10.1016\/j.isci.2020.101224","article-title":"Scalable pairwise whole-genome homology mapping of long genomes with BubbZ","volume":"23","author":"Minkin","year":"2020","journal-title":"IScience"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"4024","DOI":"10.1093\/bioinformatics\/btw609","article-title":"TwoPaCo: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes","volume":"33","author":"Minkin","year":"2017","journal-title":"Bioinformatics"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"10051","DOI":"10.18632\/oncotarget.7067","article-title":"Pan-cancer analysis of intratumor heterogeneity as a prognostic determinant of survival","volume":"7","author":"Morris","year":"2016","journal-title":"Oncotarget"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-021-02442-8","article-title":"VariantStore: an index for large-scale genomic variant search","volume":"22","author":"Pandey","year":"2021","journal-title":"Genome Biol"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1089\/cmb.2010.0252","article-title":"Cactus graphs for genome comparisons","volume":"18","author":"Paten","year":"2011","journal-title":"J. Comput. Biol"},{"key":"2023041407555222500_","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":"2023041407555222500_","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":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An eulerian path approach to DNA fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"year":"2019","author":"Polevikov","key":"2023041407555222500_"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"i205","DOI":"10.1093\/bioinformatics\/btab281","article-title":"Constructing small genome graphs via string compression","volume":"37","author":"Qiu","year":"2021","journal-title":"Bioinformatics"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-020-02157-2","article-title":"GraphAligner: rapid and versatile sequence-to-graph alignment","volume":"21","author":"Rautiainen","year":"2020","journal-title":"Genome Biol"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1026543900054","article-title":"The earth mover\u2019s distance as a metric for image retrieval","volume":"40","author":"Rubner","year":"2000","journal-title":"Int. J. Comput. Vision"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/msb.2011.75","article-title":"Fast, scalable generation of high-quality protein multiple sequence alignments using clustal omega","volume":"7","author":"Sievers","year":"2011","journal-title":"Mol. Syst. Biol"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1093\/bioinformatics\/btz575","article-title":"Haplotype-aware graph indexes","volume":"36","author":"Sir\u00e9n","year":"2020","journal-title":"Bioinformatics"},{"key":"2023041407555222500_","first-page":"47","article-title":"Markov processes over denumerable products of spaces describing large systems of automata","volume":"5","author":"Wasserstein","year":"1969","journal-title":"Probl. Inf. Transm"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1101\/gr.074492.107","article-title":"Velvet: algorithms for de novo short read assembly using de Bruijn graphs","volume":"18","author":"Zerbino","year":"2008","journal-title":"Genome Res"},{"key":"2023041407555222500_","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1093\/bib\/bby026","article-title":"Molecular subtyping of cancer: current status and moving toward clinical applications","volume":"20","author":"Zhao","year":"2019","journal-title":"Brief. Bioinform"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i404\/49886388\/btac264.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i404\/49886388\/btac264.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:28:53Z","timestamp":1700440133000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i404\/6617532"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":35,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac264","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}