{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:37:29Z","timestamp":1765233449236,"version":"3.41.2"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T00:00:00Z","timestamp":1672704000000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Beyond identifying genetic variants, we introduce a set of Boolean relations, which allows for a comprehensive classification of the relations of every pair of variants by taking all minimal alignments into account. We present an efficient algorithm to compute these relations, including a novel way of efficiently computing all minimal alignments within the best theoretical complexity bounds.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We show that these relations are common, and many non-trivial, for variants of the CFTR gene in dbSNP. Ultimately, we present an approach for the storing and indexing of variants in the context of a database that enables efficient querying for all these relations.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>A Python implementation is available at https:\/\/github.com\/mutalyzer\/algebra\/tree\/v0.2.0 as well as an interface at https:\/\/mutalyzer.nl\/algebra.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad001","type":"journal-article","created":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T21:19:56Z","timestamp":1672694396000},"source":"Crossref","is-referenced-by-count":1,"title":["A Boolean algebra for genetic variants"],"prefix":"10.1093","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5815-9116","authenticated-orcid":false,"given":"Jonathan K","family":"Vis","sequence":"first","affiliation":[{"name":"Department of Human Genetics, Leiden University Medical Center , 2333 ZC Leiden, The Netherlands"},{"name":"Leiden Institute of Advanced Computer Science, Leiden University , 2333 CA Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8414-2548","authenticated-orcid":false,"given":"Mark A","family":"Santcroos","sequence":"additional","affiliation":[{"name":"Department of Human Genetics, Leiden University Medical Center , 2333 ZC Leiden, The Netherlands"},{"name":"Department of Clinical Genetics, Leiden University Medical Center , 2333 ZC Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8860-0390","authenticated-orcid":false,"given":"Walter A","family":"Kosters","sequence":"additional","affiliation":[{"name":"Leiden Institute of Advanced Computer Science, Leiden University , 2333 CA Leiden, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8715-7371","authenticated-orcid":false,"given":"Jeroen F J","family":"Laros","sequence":"additional","affiliation":[{"name":"Department of Human Genetics, Leiden University Medical Center , 2333 ZC Leiden, The Netherlands"},{"name":"National Institute for Public Health and the Environment (RIVM) , 3721 MA Bilthoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,1,3]]},"reference":[{"key":"2023012702141743800_btad001-B1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","author":"1000 Genomes Project Consortium","year":"2015","journal-title":"Nature"},{"key":"2023012702141743800_btad001-B2","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"26","author":"Allen","year":"1983","journal-title":"Commun. ACM"},{"key":"2023012702141743800_btad001-B3","doi-asserted-by":"crossref","first-page":"W530","DOI":"10.1093\/nar\/gky355","article-title":"LitVar: a semantic search engine for linking genomic variant data in PubMed and PMC","volume":"46","author":"Allot","year":"2018","journal-title":"Nucleic Acids Res"},{"year":"2017","author":"Backurs","key":"2023012702141743800_btad001-B4"},{"key":"2023012702141743800_btad001-B5","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1093\/bioinformatics\/btw748","article-title":"Improved VCF normalization for accurate VCF comparison","volume":"33","author":"Bayat","year":"2017","journal-title":"Bioinformatics"},{"first-page":"39","year":"2000","author":"Bergroth","key":"2023012702141743800_btad001-B6"},{"key":"2023012702141743800_btad001-B7","doi-asserted-by":"crossref","first-page":"2156","DOI":"10.1093\/bioinformatics\/btr330","article-title":"The variant call format and VCFtools","volume":"27","author":"Danecek","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B8","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1002\/humu.22981","article-title":"HGVS recommendations for the description of sequence variants: 2016 update","volume":"37","author":"den Dunnen","year":"2016","journal-title":"Hum. Mutat"},{"key":"2023012702141743800_btad001-B9","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1038\/s41375-018-0372-x","article-title":"Implementation of standardized variant-calling nomenclature in the age of next-generation sequencing: where do we stand?","volume":"33","author":"Eisfeld","year":"2019","journal-title":"Leukemia"},{"key":"2023012702141743800_btad001-B10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/humu.23348","article-title":"VariantValidator: accurate validation, mapping, and formatting of sequence variation descriptions","volume":"39","author":"Freeman","year":"2018","journal-title":"Hum. Mutat"},{"year":"2002","author":"Greenberg","key":"2023012702141743800_btad001-B11"},{"year":"2003","author":"Greenberg","key":"2023012702141743800_btad001-B12"},{"key":"2023012702141743800_btad001-B13","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. Cyber"},{"key":"2023012702141743800_btad001-B14","doi-asserted-by":"crossref","first-page":"1902","DOI":"10.1093\/bioinformatics\/btz856","article-title":"SPDI: data model for variants and applications at NCBI","volume":"36","author":"Holmes","year":"2020","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B15","doi-asserted-by":"crossref","first-page":"1978","DOI":"10.1093\/bioinformatics\/bty897","article-title":"VarSome: the human genomic variant search engine","volume":"35","author":"Kopanos","year":"2019","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bioinformatics\/btt250","article-title":"Using genome query language to uncover genetic variation","volume":"30","author":"Kozanitis","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-018-1597-8","article-title":"Plyranges: a grammar of genomic data transformation","volume":"20","author":"Lee","year":"2019","journal-title":"Genome Biol"},{"key":"2023012702141743800_btad001-B18","doi-asserted-by":"crossref","first-page":"2811","DOI":"10.1093\/bioinformatics\/btab051","article-title":"Mutalyzer 2: next generation HGVS nomenclature checker","volume":"37","author":"Lefter","year":"2021","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B19","doi-asserted-by":"crossref","first-page":"1292","DOI":"10.3150\/13-BEJ522","article-title":"Optimal alignments of longest common subsequences and their path properties","volume":"20","author":"Lember","year":"2014","journal-title":"Bernoulli"},{"key":"2023012702141743800_btad001-B20","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein","year":"1966","journal-title":"Soviet Physics Doklady"},{"year":"2019","author":"Liu","key":"2023012702141743800_btad001-B21"},{"key":"2023012702141743800_btad001-B22","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour to approximate string matching","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Comput. Surv"},{"key":"2023012702141743800_btad001-B23","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.gpb.2012.06.006","article-title":"The curation of genetic variants: difficulties and possible solutions","volume":"10","author":"Pandey","year":"2012","journal-title":"Genomics Proteomics Bioinformatics"},{"key":"2023012702141743800_btad001-B24","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/3-540-44985-X_35","volume-title":"Algorithm Theory \u2014 SWAT 2000","author":"Rick","year":"2000"},{"key":"2023012702141743800_btad001-B25","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1093\/nar\/29.1.308","article-title":"dbSNP: the NCBI database of genetic variation","volume":"29","author":"Sherry","year":"2001","journal-title":"Nucleic Acids Res"},{"key":"2023012702141743800_btad001-B26","doi-asserted-by":"crossref","first-page":"2787","DOI":"10.1093\/bioinformatics\/btu345","article-title":"SMaSH: a benchmarking toolkit for human genome variant calling","volume":"30","author":"Talwalkar","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B27","doi-asserted-by":"crossref","first-page":"2202","DOI":"10.1093\/bioinformatics\/btv112","article-title":"Unified representation of genetic variants","volume":"31","author":"Tan","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B28","doi-asserted-by":"crossref","first-page":"3751","DOI":"10.1093\/bioinformatics\/btv443","article-title":"An efficient algorithm for the extraction of HGVS variant descriptions from sequences","volume":"31","author":"Vis","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B29","doi-asserted-by":"crossref","first-page":"100027","DOI":"10.1016\/j.xgen.2021.100027","article-title":"The GA4GH variation representation specification: a computational framework for variation representation and federated identification","volume":"1","author":"Wagner","year":"2021","journal-title":"Cell Genomics"},{"key":"2023012702141743800_btad001-B30","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","article-title":"The string-to-String correction problem","volume":"21","author":"Wagner","year":"1974","journal-title":"J. ACM"},{"first-page":"1226","year":"2019","author":"Watkins","key":"2023012702141743800_btad001-B31"},{"key":"2023012702141743800_btad001-B32","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btv304","article-title":"Repeat-and error-aware comparison of deletions","volume":"31","author":"Wittler","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012702141743800_btad001-B33","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(90)90035-V","article-title":"An O(NP) sequence comparison algorithm","volume":"35","author":"Wu","year":"1990","journal-title":"Inf. Process. Lett"},{"key":"2023012702141743800_btad001-B34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13073-016-0396-7","article-title":"A variant by any name: quantifying annotation discordance across tools and clinical databases","volume":"9","author":"Yen","year":"2017","journal-title":"Genome Med"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad001\/48481232\/btad001.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btad001\/48909273\/btad001.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/1\/btad001\/48909273\/btad001.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,19]],"date-time":"2023-03-19T19:55:46Z","timestamp":1679255746000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad001\/6967432"}},"subtitle":[],"editor":[{"given":"Tobias","family":"Marschall","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad001","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2023,1,1]]},"published":{"date-parts":[[2023,1,1]]},"article-number":"btad001"}}