{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T09:46:53Z","timestamp":1742636813214,"version":"3.37.3"},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"24","funder":[{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,12,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Why recombination? is one of the central questions in biology. This has led to a host of methods for quantifying recombination from sequence data. These methods are usually based on aligned DNA sequences. Here, we propose an efficient alignment-free alternative.<\/jats:p><jats:p>Results: Our method is based on the distribution of match lengths, which we look up using enhanced suffix arrays. By eliminating the alignment step, the test becomes fast enough for application to whole bacterial genomes. Using simulations we show that our test has similar power as established tests when applied to long pairs of sequences. When applied to 58 genomes of Escherichia coli, we pick up the strongest recombination signal from a 125 kb horizontal gene transfer engineered 20 years ago.<\/jats:p><jats:p>Availability and implementation: We have implemented our method in the command-line program rush. Its C sources and documentation are available under the GNU General Public License from http:\/\/guanine.evolbio.mpg.de\/rush\/.<\/jats:p><jats:p>Contact: \u00a0haubold@evolbio.mpg.de<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt550","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T03:45:09Z","timestamp":1380080709000},"page":"3121-3127","source":"Crossref","is-referenced-by-count":8,"title":["An alignment-free test for recombination"],"prefix":"10.1093","volume":"29","author":[{"given":"Bernhard","family":"Haubold","sequence":"first","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, 2Institute for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 79104 Freiburg, Germany"}]},{"given":"Linda","family":"Krause","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, 2Institute for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 79104 Freiburg, Germany"},{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, 2Institute for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 79104 Freiburg, Germany"}]},{"given":"Thomas","family":"Horn","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, 2Institute for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 79104 Freiburg, Germany"}]},{"given":"Peter","family":"Pfaffelhuber","sequence":"additional","affiliation":[{"name":"1 Department of Evolutionary Genetics, Max-Planck-Institute for Evolutionary Biology, 24306 Pl\u00f6n, 2Institute for Neuro- and Bioinformatics, L\u00fcbeck University, 23562 L\u00fcbeck and 3Mathematical Stochastics, Mathematical Institute, Freiburg University, 79104 Freiburg, Germany"}]}],"member":"286","published-online":{"date-parts":[[2013,9,23]]},"reference":[{"key":"2023012810495223300_btt550-B1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-45784-4_35","article-title":"The enhanced suffix array and its applications to genome analysis","volume-title":"Proceedings of the Second Workshop on Algorithms in Bioinformatics","author":"Abouelhoda","year":"2002"},{"key":"2023012810495223300_btt550-B2","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1038\/nrmicro909","article-title":"From pieces to patterns: evolutionary engineering in bacterial pathogens","volume":"2","author":"Baquero","year":"2004","journal-title":"Nat. Revi. Microbiol."},{"key":"2023012810495223300_btt550-B3","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1101\/gr.1960404","article-title":"MAVID: constrained ancestral alignment of multiple sequences","volume":"14","author":"Bray","year":"2004","journal-title":"Genome Res."},{"key":"2023012810495223300_btt550-B4","doi-asserted-by":"crossref","first-page":"2665","DOI":"10.1534\/genetics.105.048975","article-title":"A simple and robust statistical test for detecting the presence of recombination","volume":"172","author":"Bruen","year":"2006","journal-title":"Genetics"},{"key":"2023012810495223300_btt550-B5","doi-asserted-by":"crossref","first-page":"1394","DOI":"10.1101\/gr.2289704","article-title":"Mauve: multiple alignment of conserved genomic sequence with rearrangement","volume":"14","author":"Darling","year":"2004","journal-title":"Genome Res."},{"key":"2023012810495223300_btt550-B6","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1534\/genetics.110.120121","article-title":"Inference of homologous recombination in bacteria using whole genome sequences","volume":"186","author":"Didelot","year":"2010","journal-title":"Genetics"},{"key":"2023012810495223300_btt550-B7","doi-asserted-by":"crossref","first-page":"3221","DOI":"10.1093\/bioinformatics\/btp590","article-title":"Efficient estimation of pairwise distances between genomes","volume":"25","author":"Domazet-Lo\u0161o","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012810495223300_btt550-B8","doi-asserted-by":"crossref","first-page":"1466","DOI":"10.1093\/bioinformatics\/btr176","article-title":"Alignment-free detection of local similarity among viral and bacterial genomes","volume":"27","author":"Domazet-Lo\u0161o","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012810495223300_btt550-B9","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1093\/genetics\/78.2.737","article-title":"The evolutionary advantage of recombination","volume":"78","author":"Felsenstein","year":"1974","journal-title":"Genetics"},{"article-title":"PHYLIP (phylogeny interference package) version 3.6","year":"2005","author":"Felsenstein","key":"2023012810495223300_btt550-B10"},{"key":"2023012810495223300_btt550-B11","doi-asserted-by":"crossref","DOI":"10.5962\/bhl.title.27468","volume-title":"The Genetical Theory of Natural Selection","author":"Fisher","year":"1930\/1999","edition":"Variorum edn"},{"key":"2023012810495223300_btt550-B12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023012810495223300_btt550-B13","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1534\/g3.112.002527","article-title":"Alignment-free population genomics: an efficient estimator of sequence diversity","volume":"2","author":"Haubold","year":"2012","journal-title":"Genes Genomes Genet."},{"key":"2023012810495223300_btt550-B14","doi-asserted-by":"crossref","first-page":"1487","DOI":"10.1089\/cmb.2009.0106","article-title":"Estimating mutation distances from unaligned genomes","volume":"16","author":"Haubold","year":"2009","journal-title":"J. Comput. Biol."},{"key":"2023012810495223300_btt550-B15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1186\/1471-2105-6-123","article-title":"Genome comparison without alignment using shortest unique substrings","volume":"6","author":"Haubold","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012810495223300_btt550-B16","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1093\/bioinformatics\/btq689","article-title":"Alignment-free estimation of nucleotide diversity","volume":"27","author":"Haubold","year":"2011","journal-title":"Bioinformatics"},{"key":"2023012810495223300_btt550-B17","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1093\/genetics\/109.3.611","article-title":"The sampling distribution of linkage disequilibrium under an infinite allele model without selection","volume":"109","author":"Hudson","year":"1985","journal-title":"Genetics"},{"key":"2023012810495223300_btt550-B18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under a Wright-Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012810495223300_btt550-B19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1093\/genetics\/111.1.147","article-title":"Statistical properties of the number of recombination events in the history of a sample of DNA sequences","volume":"111","author":"Hudson","year":"1985","journal-title":"Genetics"},{"key":"2023012810495223300_btt550-B20","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":"2023012810495223300_btt550-B21","first-page":"698","article-title":"Engineering a lightweight suffix array construction algorithm","volume-title":"ESA\u201902: Proceedings of the 10th Annual European Symposium on Algorithms","author":"Manzini","year":"2002"},{"key":"2023012810495223300_btt550-B22","first-page":"126","article-title":"Analysing the mosaic structure of genes","volume":"34","author":"Maynard Smith","year":"1992","journal-title":"J. Mol. Evol."},{"key":"2023012810495223300_btt550-B23","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1086\/280418","article-title":"Some genetic aspects of sex","volume":"66","author":"Muller","year":"1932","journal-title":"Am. Nat."},{"key":"2023012810495223300_btt550-B24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0027-5107(64)90047-8","article-title":"The relation of recombination to mutational advance","volume":"1","author":"Muller","year":"1964","journal-title":"Mutat. Res."},{"key":"2023012810495223300_btt550-B25","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1128\/aem.57.4.893-900.1991","article-title":"Genetic improvement of Escherichia coli for ethanol production: chromosomal integration of zymomonas mobilis genes encoding pyruvate decarboxylase and alcohol dehydrogenase II","volume":"57","author":"Ohta","year":"1991","journal-title":"Appl. Environ. Microbiol."},{"key":"2023012810495223300_btt550-B26","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1017\/S001667230800966X","article-title":"Unravelling the evolutionary advantage of sex: a commentary on \u2018Mutation-selection balance and the evolutionary advantage of sex and recombination\u2019 by Brian Charlesworth","volume":"89","author":"Otto","year":"2007","journal-title":"Genet. Res. Camb."},{"key":"2023012810495223300_btt550-B27","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1038\/nrg761","article-title":"Resolving the paradox of sex and recombination","volume":"3","author":"Otto","year":"2002","journal-title":"Nat. Rev. Genet."},{"key":"2023012810495223300_btt550-B28","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1093\/oxfordjournals.molbev.a004129","article-title":"Evaluation of methods for detecting recombination from DNA sequences: empirical data","volume":"19","author":"Posada","year":"2002","journal-title":"Mol. Biol. Evol."},{"key":"2023012810495223300_btt550-B29","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/1242471.1242472","article-title":"A taxonomy of suffix array construction algorithms","volume":"39","author":"Puglisi","year":"2007","journal-title":"ACM Comput. Surv."},{"key":"2023012810495223300_btt550-B30","first-page":"526","article-title":"Statistical tests for detecting gene conversion","volume":"6","author":"Sawyer","year":"1989","journal-title":"Mol. Biol. Evol."},{"key":"2023012810495223300_btt550-B31","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s10295-011-1052-2","article-title":"Optical mapping and sequencing of the Escherichia coli KO11 genome reveal extensive chromosomal rearrangements, and multiple tandem copies of the Zymomonas mobilis pdc and adhB genes","volume":"39","author":"Turner","year":"2012","journal-title":"J. Ind. Microbiol. Biotechnol."},{"volume-title":"Coalescent Theory: An Introduction","year":"2009","author":"Wakeley","key":"2023012810495223300_btt550-B32"},{"key":"2023012810495223300_btt550-B33","doi-asserted-by":"crossref","first-page":"1929","DOI":"10.1093\/oxfordjournals.molbev.a003733","article-title":"A simulation study of the reliability of recombinaiton detection methods","volume":"18","author":"Wiuf","year":"2001","journal-title":"Mol. Biol. Evol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/24\/3121\/48898835\/bioinformatics_29_24_3121.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/24\/3121\/48898835\/bioinformatics_29_24_3121.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T20:41:16Z","timestamp":1688503276000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/24\/3121\/194118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,23]]},"references-count":33,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2013,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt550","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2013,12,15]]},"published":{"date-parts":[[2013,9,23]]}}}