{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T18:58:59Z","timestamp":1770231539823,"version":"3.49.0"},"reference-count":34,"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":909,"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>\n               <jats:p>Motivation: Alignment-based methods for sequence analysis have various limitations if large datasets are to be analysed. Therefore, alignment-free approaches have become popular in recent years. One of the best known alignment-free methods is the average common substring approach that defines a distance measure on sequences based on the average length of longest common words between them. Herein, we generalize this approach by considering longest common substrings with k mismatches. We present a greedy heuristic to approximate the length of such k -mismatch substrings, and we describe kmacs , an efficient implementation of this idea based on generalized enhanced suffix arrays.<\/jats:p>\n               <jats:p>Results: To evaluate the performance of our approach, we applied it to phylogeny reconstruction using a large number of DNA and protein sequence sets. In most cases, phylogenetic trees calculated with kmacs were more accurate than trees produced with established alignment-free methods that are based on exact word matches. Especially on protein sequences, our method seems to be superior. On simulated protein families, kmacs even outperformed a classical approach to phylogeny reconstruction using multiple alignment and maximum likelihood.<\/jats:p>\n               <jats:p>Availability and implementation: \u00a0kmacs is implemented in C++, and the source code is freely available at http:\/\/kmacs.gobics.de\/<\/jats:p>\n               <jats:p>Contact: \u00a0chris.leimeister@stud.uni-goettingen.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu331","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T00:49:00Z","timestamp":1400114940000},"page":"2000-2008","source":"Crossref","is-referenced-by-count":106,"title":["kmacs: the \n            <i>k<\/i>\n            -mismatch average common substring approach to alignment-free sequence comparison"],"prefix":"10.1093","volume":"30","author":[{"given":"Chris-Andre","family":"Leimeister","sequence":"first","affiliation":[{"name":"1 Department of Bioinformatics, Institute of Microbiology and Genetics, University of G\u00f6ttingen, Goldschmidtstr. 1, 37073 G\u00f6ttingen, Germany and 2 Laboratoire Statistique et G\u00e9nome, Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, UMR CNRS 8071, USC INRA, 23 Boulevard de France, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[{"name":"1 Department of Bioinformatics, Institute of Microbiology and Genetics, University of G\u00f6ttingen, Goldschmidtstr. 1, 37073 G\u00f6ttingen, Germany and 2 Laboratoire Statistique et G\u00e9nome, Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, UMR CNRS 8071, USC INRA, 23 Boulevard de France, 91037 \u00c9vry, France"},{"name":"1 Department of Bioinformatics, Institute of Microbiology and Genetics, University of G\u00f6ttingen, Goldschmidtstr. 1, 37073 G\u00f6ttingen, Germany and 2 Laboratoire Statistique et G\u00e9nome, Universit\u00e9 d\u2019\u00c9vry Val d\u2019Essonne, UMR CNRS 8071, USC INRA, 23 Boulevard de France, 91037 \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,5,13]]},"reference":[{"issue":"1","key":"2023012711245611300_btu331-B1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discrete Algorithms"},{"key":"2023012711245611300_btu331-B2","first-page":"64","article-title":"Computing longest common substrings via suffix arrays","volume-title":"Computer Science - Theory and Applications, volume 5010 of Lecture Notes in Computer Science","author":"Babenko","year":"2008"},{"key":"2023012711245611300_btu331-B3","first-page":"21","article-title":"Alignment-free sequence comparison with spaced \n              k\n              -mers","volume-title":"Proceedings German Conference on Bioinformatics (GCB\u201913)","author":"Boden","year":"2013"},{"key":"2023012711245611300_btu331-B4","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":"2023012711245611300_btu331-B5","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":"2023012711245611300_btu331-B6","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":"2023012711245611300_btu331-B7","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":"2023012711245611300_btu331-B8","first-page":"164","article-title":"PHYLIP - Phylogeny Inference Package (Version 3.2)","volume":"5","author":"Felsenstein","year":"1989","journal-title":"Cladistics"},{"key":"2023012711245611300_btu331-B9","first-page":"374","article-title":"Inducing the LCP-array","volume-title":"Proceedings of 12th Algorithms and Data Structures Symposium, Lecture Notes in Computer Science 6844","author":"Fischer","year":"2011"},{"key":"2023012711245611300_btu331-B10","first-page":"36","article-title":"Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE","volume-title":"Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science 4009","author":"Fischer","year":"2006"},{"key":"2023012711245611300_btu331-B11","first-page":"459","article-title":"A new succinct representation of RMQ-information and improvements in the enhanced suffix array","volume-title":"Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science 4614","author":"Fischer","year":"2007"},{"key":"2023012711245611300_btu331-B12","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast algorithms for finding nearest common ancestor","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"2023012711245611300_btu331-B13","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":"2023012711245611300_btu331-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":"2023012711245611300_btu331-B15","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":"2023012711245611300_btu331-B16","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gku398","article-title":"Spaced words\n               and \n              kmacs\n              : fast alignment-free sequence comparison based on inexact word matches","author":"Horwege","year":"2014","journal-title":"Nucleic Acids Res."},{"key":"2023012711245611300_btu331-B17","doi-asserted-by":"crossref","first-page":"1991","DOI":"10.1093\/bioinformatics\/btu177","article-title":"Fast alignment-free sequence comparison using spaced-word frequencies","volume":"30","author":"Leimeister","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012711245611300_btu331-B18","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":"2023012711245611300_btu331-B19","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":"2023012711245611300_btu331-B20","first-page":"319","article-title":"Suffix arrays: a new method for on-line string searches","volume-title":"Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, SODA\u201990","author":"Manber","year":"1990"},{"key":"2023012711245611300_btu331-B21","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1038\/ismej.2009.150","article-title":"Genome characteristics of a generalist marine bacterial lineage","volume":"4","author":"Newton","year":"2010","journal-title":"ISME J"},{"key":"2023012711245611300_btu331-B22","first-page":"193","article-title":"Linear suffix array construction by almost pure induced-sorting","volume-title":"Proceedings of 19th IEEE Data Compression Conference (IEEE DCC)","author":"Nong","year":"2009"},{"key":"2023012711245611300_btu331-B23","doi-asserted-by":"crossref","first-page":"W45","DOI":"10.1093\/nar\/gkh362","article-title":"CVTree: a phylogenetic tree reconstruction tool based on whole genomes","volume":"32","author":"Qi","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012711245611300_btu331-B24","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":"2023012711245611300_btu331-B25","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":"2023012711245611300_btu331-B26","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":"2023012711245611300_btu331-B27","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."},{"key":"2023012711245611300_btu331-B28","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":"2023012711245611300_btu331-B29","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":"2023012711245611300_btu331-B30","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":"2023012711245611300_btu331-B31","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"2023012711245611300_btu331-B32","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."},{"issue":"4","key":"2023012711245611300_btu331-B33","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":"2023012711245611300_btu331-B34","first-page":"1","article-title":"Linear pattern matching algorithms","volume-title":"Proceedings of the 14th IEEE Symposium on Switching and Automata Theory","author":"Weiner","year":"1973"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/2000\/48924929\/bioinformatics_30_14_2000.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/14\/2000\/48924929\/bioinformatics_30_14_2000.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T11:55:54Z","timestamp":1674820554000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/14\/2000\/2391348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,13]]},"references-count":34,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu331","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,5,13]]}}}