{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:56:25Z","timestamp":1742637385905},"reference-count":12,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2016,12,28]],"date-time":"2016-12-28T00:00:00Z","timestamp":1482883200000},"content-version":"vor","delay-in-days":796,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,3,1]]},"abstract":"<jats:p>Motivation: Single nucleotide polymorphism (SNP) discovery is an important preliminary for understanding genetic variation. With current sequencing methods, we can sample genomes comprehensively. SNPs are found by aligning sequence reads against longer assembled references. De Bruijn graphs are efficient data structures that can deal with the vast amount of data from modern technologies. Recent work has shown that the topology of these graphs captures enough information to allow the detection and characterization of genetic variants, offering an alternative to alignment-based methods. Such methods rely on depth-first walks of the graph to identify closing bifurcations. These methods are conservative or generate many false-positive results, particularly when traversing highly inter-connected (complex) regions of the graph or in regions of very high coverage.<\/jats:p>\n               <jats:p>Results: We devised an algorithm that calls SNPs in converted De Bruijn graphs by enumerating 2k\u2009+\u20092 cycles. We evaluated the accuracy of predicted SNPs by comparison with SNP lists from alignment-based methods. We tested accuracy of the SNP calling using sequence data from 16 ecotypes of Arabidopsis thaliana and found that accuracy was high. We found that SNP calling was even across the genome and genomic feature types. Using sequence-based attributes of the graph to train a decision tree allowed us to increase accuracy of SNP calls further. Together these results indicate that our algorithm is capable of finding SNPs accurately in complex sub-graphs and potentially comprehensively from whole genome graphs.<\/jats:p>\n               <jats:p>Availability and implementation: The source code for a C++ implementation of our algorithm is available under the GNU Public Licence v3 at: https:\/\/github.com\/danmaclean\/2kplus2. The datasets used in this study are available at the European Nucleotide Archive, reference ERP00565, http:\/\/www.ebi.ac.uk\/ena\/data\/view\/ERP000565<\/jats:p>\n               <jats:p>Contact: \u00a0dan.maclean@tsl.ac.uk<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary Data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu706","type":"journal-article","created":{"date-parts":[[2014,10,25]],"date-time":"2014-10-25T03:54:31Z","timestamp":1414209271000},"page":"642-646","source":"Crossref","is-referenced-by-count":6,"title":["Using 2<i>k<\/i>\u2009+\u20092 bubble searches to find single nucleotide polymorphisms in <i>k<\/i>-mer graphs"],"prefix":"10.1093","volume":"31","author":[{"given":"Reda","family":"Younsi","sequence":"first","affiliation":[{"name":"1The Sainsbury Laboratory, Norwich Research Park, Norwich NR4 7UH, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"MacLean","sequence":"additional","affiliation":[{"name":"1The Sainsbury Laboratory, Norwich Research Park, Norwich NR4 7UH, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,10,24]]},"reference":[{"key":"2023020116162563200_btu706-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023020116162563200_btu706-B3","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1038\/nature10414","article-title":"Multiple reference genomes and transcriptomes for Arabidopsis thaliana","volume":"477","author":"Gan","year":"2011","journal-title":"Nature"},{"key":"2023020116162563200_btu706-B4","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1656274.1656278","article-title":"The WEKA data mining software: an update","volume":"11","author":"Hall","year":"2009","journal-title":"ACM SIGKDD Explor. Newsl."},{"key":"2023020116162563200_btu706-B5","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De\u00a0novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"key":"2023020116162563200_btu706-B6","doi-asserted-by":"crossref","first-page":"S10","DOI":"10.1186\/1471-2164-15-S4-S10","article-title":"Reference-free SNP detection: dealing with the data deluge","volume":"15","author":"Leggett","year":"2014","journal-title":"BMC Genomics"},{"key":"2023020116162563200_btu706-B7","author":"Leggett","year":"2013"},{"key":"2023020116162563200_btu706-B10","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/978-3-642-16321-0_14","article-title":"Identifying SNPs without a reference genome by comparing raw reads","volume":"6393","author":"Peterlongo","year":"2010","journal-title":"Lect. Notes Comput. Sci."},{"key":"2023020116162563200_btu706-B11","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"},{"key":"2023020116162563200_btu706-B12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF00116251","article-title":"Induction of decision trees","volume":"1","author":"Quinlan","year":"1986","journal-title":"Mach. Learn."},{"key":"2023020116162563200_btu706-B14","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1101\/gr.089532.108","article-title":"ABySS: a parallel assembler for short read sequence data","volume":"19","author":"Simpson","year":"2009","journal-title":"Genome Res."},{"key":"2023020116162563200_btu706-B15","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1038\/35048692","article-title":"Analysis of the genome sequence of the flowering plant Arabidopsis thaliana","volume":"408","author":"The Arabidopsis Genome Initiative","year":"2000","journal-title":"Nature"},{"key":"2023020116162563200_btu706-B16","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."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/5\/642\/49011486\/bioinformatics_31_5_642.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/5\/642\/49011486\/bioinformatics_31_5_642.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:27:43Z","timestamp":1675297663000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/5\/642\/2748197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,24]]},"references-count":12,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu706","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,24]]}}}