{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T01:12:34Z","timestamp":1774746754692,"version":"3.50.1"},"reference-count":52,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2016,11,7]],"date-time":"2016-11-07T00:00:00Z","timestamp":1478476800000},"content-version":"vor","delay-in-days":949,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Alignment-free methods for sequence comparison are increasingly used for genome analysis and phylogeny reconstruction; they circumvent various difficulties of traditional alignment-based approaches. In particular, alignment-free methods are much faster than pairwise or multiple alignments. They are, however, less accurate than methods based on sequence alignment. Most alignment-free approaches work by comparing the word composition of sequences. A well-known problem with these methods is that neighbouring word matches are far from independent.<\/jats:p><jats:p>Results: To reduce the statistical dependency between adjacent word matches, we propose to use \u2018spaced words\u2019, defined by patterns of \u2018match\u2019 and \u2018don\u2019t care\u2019 positions, for alignment-free sequence comparison. We describe a fast implementation of this approach using recursive hashing and bit operations, and we show that further improvements can be achieved by using multiple patterns instead of single patterns. To evaluate our approach, we use spaced-word frequencies as a basis for fast phylogeny reconstruction. Using real-world and simulated sequence data, we demonstrate that our multiple-pattern approach produces better phylogenies than approaches relying on contiguous words.<\/jats:p><jats:p>Availability and implementation: Our program is freely available at http:\/\/spaced.gobics.de\/.<\/jats:p><jats:p>Contact: \u00a0chris.leimeister@stud.uni-goettingen.de<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu177","type":"journal-article","created":{"date-parts":[[2014,4,4]],"date-time":"2014-04-04T01:54:59Z","timestamp":1396576499000},"page":"1991-1999","source":"Crossref","is-referenced-by-count":116,"title":["Fast alignment-free sequence comparison using spaced-word frequencies"],"prefix":"10.1093","volume":"30","author":[{"given":"Chris-Andre","family":"Leimeister","sequence":"first","affiliation":[{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Boden","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Horwege","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Lindner","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"},{"name":"1 Department of Bioinformatics, University of G\u00f6ttingen, Institute of Microbiology and Genetics, 37073 G\u00f6ttingen, Germany and 2 Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, Laboratoire Statistique et G\u00e9nome, UMR CNRS 8071, USC INRA, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,4,3]]},"reference":[{"key":"2023012711271281000_btu177-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":"2023012711271281000_btu177-B2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1186\/1748-7188-5-21","article-title":"Sequence embedding for fast construction of guide trees for multiple sequence alignment","volume":"5","author":"Blackshields","year":"2010","journal-title":"Algorithms Mol. Biol."},{"key":"2023012711271281000_btu177-B3","article-title":"Alignment-free sequence comparison with spaced k -mers","volume-title":"German Conference on Bioinformatics 2013","author":"Boden","year":"2013"},{"key":"2023012711271281000_btu177-B4","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1002\/9780470253441.ch6","article-title":"A survey of seeding for sequence alignment","volume-title":"Bioinformatics Algorithms: Techniques and Applications","author":"Brown","year":"2008"},{"key":"2023012711271281000_btu177-B5","doi-asserted-by":"crossref","first-page":"R108","DOI":"10.1186\/gb-2009-10-10-r108","article-title":"Genomic DNA k -mer spectra: models and modalities","volume":"10","author":"Chor","year":"2009","journal-title":"Genome Biol."},{"key":"2023012711271281000_btu177-B6","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/256163.256168","article-title":"Recursive hashing functions for n-grams","volume":"15","author":"Cohen","year":"1997","journal-title":"ACM Trans. Inf. Syst."},{"key":"2023012711271281000_btu177-B7","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1186\/1748-7188-7-34","article-title":"Alignment-free phylogeny of whole genomes using underlying subwords","volume":"7","author":"Comin","year":"2012","journal-title":"Algorithms Mol. Biol."},{"key":"2023012711271281000_btu177-B8","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1186\/1471-2105-11-406","article-title":"MS4\u2014multi-scale selector of sequence signatures: an alignment-free method for classification of biological sequences","volume":"11","author":"Corel","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023012711271281000_btu177-B9","doi-asserted-by":"crossref","first-page":"e11147","DOI":"10.1371\/journal.pone.0011147","article-title":"progressiveMauve: multiple genome alignment with gene gain, loss and rearrangement","volume":"5","author":"Darling","year":"2010","journal-title":"PLoS One"},{"key":"2023012711271281000_btu177-B10","first-page":"345","article-title":"A model of evolutionary change in proteins","volume":"6","author":"Dayhoff","year":"1978","journal-title":"Atlas Protein Seq. Struct."},{"key":"2023012711271281000_btu177-B11","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0304-3975(97)00122-9","article-title":"Caract\u00e9risation des N -\u00e9critures et application \u00e0\u2019l \u00e9tude des suites de complexit\u00e9 ultimement n + c st","volume":"215","author":"Didier","year":"1999","journal-title":"Theor. Comp. Sci."},{"key":"2023012711271281000_btu177-B12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-8-1","article-title":"Comparing sequences without using alignments: application to HIV\/SIV subtyping","volume":"8","author":"Didier","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023012711271281000_btu177-B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2012.08.005","article-title":"Variable length local decoding and alignment-free sequence comparison","volume":"462","author":"Didier","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"2023012711271281000_btu177-B14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1186\/1471-2148-9-157","article-title":"HaMStR: profile hidden markov model based search for orthologs in ESTs","volume":"9","author":"Ebersberger","year":"2009","journal-title":"BMC Evol. Biol."},{"key":"2023012711271281000_btu177-B15","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: Multiple sequence alignment with high score accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012711271281000_btu177-B16","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Evolutionary trees from DNA sequences: a maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J. Mol. Evol."},{"key":"2023012711271281000_btu177-B17","first-page":"164","article-title":"PHYLIP\u2014Phylogeny Inference Package (Version 3.2)","volume":"5","author":"Felsenstein","year":"1989","journal-title":"Cladistics"},{"key":"2023012711271281000_btu177-B18","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2003"},{"key":"2023012711271281000_btu177-B19","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1093\/bioinformatics\/bts028","article-title":"Estimation of pairwise sequence similarity of mammalian enhancers with word neighbourhood counts","volume":"28","author":"G\u00f6ke","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B20","doi-asserted-by":"crossref","first-page":"192","DOI":"10.3389\/fpls.2012.00192","article-title":"A phylogenetic analysis of the brassicales clade based on an alignment-free sequence comparison method","volume":"3","author":"Hatje","year":"2012","journal-title":"Front. Plant Sci."},{"key":"2023012711271281000_btu177-B21","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":"2023012711271281000_btu177-B22","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":"2023012711271281000_btu177-B23","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1186\/1471-2105-14-248","article-title":"kClust: fast and sensitive clustering of large protein sequence databases","volume":"14","author":"Hauser","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023012711271281000_btu177-B24","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1177\/117693430600200016","article-title":"Pattern-based phylogenetic distance estimation and tree reconstruction","volume":"2","author":"H\u00f6hl","year":"2006","journal-title":"Evol. Bioinform. Online"},{"key":"2023012711271281000_btu177-B52","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gku398","article-title":"Spaced words and kmacs: fast alignment-free sequence comparison based on inexact word matches","author":"Horwege","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023012711271281000_btu177-B25","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM J. Res. Dev."},{"key":"2023012711271281000_btu177-B26","doi-asserted-by":"crossref","first-page":"3059","DOI":"10.1093\/nar\/gkf436","article-title":"MAFFT: a novel method for rapid multiple sequence alignment based on fast fourier transform","volume":"30","author":"Katoh","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023012711271281000_btu177-B27","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0166-218X(03)00382-2","article-title":"On spaced seeds for similarity search","volume":"138","author":"Keich","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"2023012711271281000_btu177-B28","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1016\/j.ympev.2012.07.003","article-title":"Alignment-free distance measure based on return time distribution for sequence analysis: applications to clustering, molecular phylogeny and subtyping","volume":"65","author":"Kolekar","year":"2012","journal-title":"Mol. Phylogenet. Evol."},{"key":"2023012711271281000_btu177-B29","first-page":"340","article-title":"The kullbackleibler distance","volume":"41","author":"Kullback","year":"1987","journal-title":"Am. Stat."},{"key":"2023012711271281000_btu177-B51","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1093\/bioinformatics\/btu331","article-title":"kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison","volume":"30","author":"Leimeister","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B30","first-page":"164","article-title":"PatternHunter II: highly sensitive and fast homology search","volume":"14","author":"Li","year":"2003","journal-title":"Genome Inform."},{"key":"2023012711271281000_btu177-B31","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/18.61115","article-title":"Divergence measures based on the shannon entropy","volume":"37","author":"Lin","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023012711271281000_btu177-B32","doi-asserted-by":"crossref","first-page":"2224","DOI":"10.1093\/bioinformatics\/btl376","article-title":"Remote homology detection based on oligomer distances","volume":"22","author":"Lingner","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B33","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B34","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0893-9659(01)00085-4","article-title":"A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences","volume":"15","author":"Morgenstern","year":"2002","journal-title":"Appl. Math. Lett."},{"key":"2023012711271281000_btu177-B35","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"2023012711271281000_btu177-B36","volume-title":"DNA, Words and Models: Statistics of Exceptional Words","author":"Robin","year":"2005"},{"key":"2023012711271281000_btu177-B37","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci."},{"key":"2023012711271281000_btu177-B38","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol."},{"key":"2023012711271281000_btu177-B39","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1186\/1471-2105-10-219","article-title":"Orthoselect: a protocol for selecting orthologous groups in phylogenomics","volume":"10","author":"Schreiber","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023012711271281000_btu177-B40","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":"2023012711271281000_btu177-B41","doi-asserted-by":"crossref","first-page":"2677","DOI":"10.1073\/pnas.0813249106","article-title":"Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions","volume":"106","author":"Sims","year":"2009","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012711271281000_btu177-B42","first-page":"1409","article-title":"A Statistical Method for Evaluating Systematic Relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"University of Kansas Science Bulletin"},{"key":"2023012711271281000_btu177-B43","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1089\/cmb.2012.0228","article-title":"Alignment-free sequence comparison based on next generation sequencing reads","volume":"20","author":"Song","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023012711271281000_btu177-B44","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1093\/bioinformatics\/14.2.157","article-title":"Rose: generating sequence families","volume":"14","author":"Stoye","year":"1998","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B45","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023012711271281000_btu177-B46","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/prot.20527","article-title":"BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark","volume":"61","author":"Thompson","year":"2005","journal-title":"Proteins"},{"key":"2023012711271281000_btu177-B47","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"Ulitsky","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012711271281000_btu177-B48","article-title":"Hashing concepts and the java programming language","volume-title":"Technical report","author":"Uzgalis","year":"1996"},{"key":"2023012711271281000_btu177-B49","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1093\/bioinformatics\/btg005","article-title":"Alignment-free sequence comparison\u2014a review","volume":"19","author":"Vinga","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012711271281000_btu177-B50","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/1748-7188-7-10","article-title":"Pattern matching through Chaos Game Representation: bridging numerical and discrete data structures for biological sequence analysis","volume":"7","author":"Vinga","year":"2012","journal-title":"Algorithms Mol. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/1991\/48925419\/bioinformatics_30_14_1991.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/1991\/48925419\/bioinformatics_30_14_1991.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T16:55:33Z","timestamp":1716656133000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/14\/1991\/2391234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,3]]},"references-count":52,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu177","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,7,15]]},"published":{"date-parts":[[2014,4,3]]}}}