{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:46Z","timestamp":1759639006275},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T00:00:00Z","timestamp":1513296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Alignment-free sequence comparison methods can compute the pairwise similarity between a huge number of sequences much faster than sequence-alignment based methods.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We propose a new non-parametric alignment-free sequence comparison method, called K2, based on the Kendall statistics. Comparing to the other state-of-the-art alignment-free comparison methods, K2 demonstrates competitive performance in generating the phylogenetic tree, in evaluating functionally related regulatory sequences, and in computing the edit distance (similarity\/dissimilarity) between sequences. Furthermore, the K2 approach is much faster than the other methods. An improved method, K2*, is also proposed, which is able to determine the appropriate algorithmic parameter (length) automatically, without first considering different values. Comparative analysis with the state-of-the-art alignment-free sequence similarity methods demonstrates the superiority of the proposed approaches, especially with increasing sequence length, or increasing dataset sizes.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The K2 and K2* approaches are implemented in the R language as a package and is freely available for open access (http:\/\/community.wvu.edu\/daadjeroh\/projects\/K2\/K2_1.0.tar.gz).<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx809","type":"journal-article","created":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T20:11:53Z","timestamp":1513282313000},"page":"1682-1689","source":"Crossref","is-referenced-by-count":8,"title":["<i>K<\/i>\n     \u00a02 and K2*: efficient alignment-free sequence similarity measurement based on Kendall statistics"],"prefix":"10.1093","volume":"34","author":[{"given":"Jie","family":"Lin","sequence":"first","affiliation":[{"name":"Department of Software engineering, College of Mathematics and Informatics, Fujian Normal University, Fuzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald A","family":"Adjeroh","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Electrical Engineering, West Virginia University, Morgantown, WV, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing-Hua","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Pathology, Carver College of Medicine, The University of Iowa, Iowa City, IA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Software engineering, College of Mathematics and Informatics, Fujian Normal University, Fuzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"2023012713441864600_btx809-B1","first-page":"5","article-title":"Computational comparison of two draft sequences of the human genome","volume":"26","author":"Aach","year":"2001","journal-title":"Nature"},{"key":"2023012713441864600_btx809-B2","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-78909-5","volume-title":"The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching","author":"Adjeroh","year":"2008","edition":"1st edn"},{"key":"2023012713441864600_btx809-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-5-18","article-title":"Robinson foulds supertrees","volume":"5","author":"Bansal","year":"2010","journal-title":"Algorithms Mol. Biol"},{"key":"2023012713441864600_btx809-B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-15-321","article-title":"An improved alignment-free model for DNA sequence similarity metric","volume":"15","author":"Bao","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023012713441864600_btx809-B5","doi-asserted-by":"crossref","first-page":"19163","DOI":"10.4238\/2015.December.29.26","article-title":"A wavelet-based feature vector model for DNA clustering","volume":"14","author":"Bao","year":"2015","journal-title":"Genet. Mol. Res. GMR"},{"key":"2023012713441864600_btx809-B6","doi-asserted-by":"crossref","first-page":"48.","DOI":"10.1186\/1471-2105-9-48","article-title":"The average mutual information profile as a genomic signature","volume":"9","author":"Bauer","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012713441864600_btx809-B7","first-page":"92","author":"Beal","year":"2016"},{"key":"2023012713441864600_btx809-B8","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1186\/s12864-016-2793-0","article-title":"A new algorithm for the LCS problem with application in compressing genome resequencing data","volume":"17","author":"Beal","year":"2016","journal-title":"BMC Genomics"},{"key":"2023012713441864600_btx809-B9","doi-asserted-by":"crossref","first-page":"5155","DOI":"10.1073\/pnas.83.14.5155","article-title":"A measure of the similarity of sets of sequences not requiring sequence alignment","volume":"83","author":"Blaisdell","year":"1986","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012713441864600_btx809-B10","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1093\/bib\/bbt052","article-title":"Alignment-free genetic sequence comparisons: a review of recent approaches by word analysis","volume":"15","author":"Bonham-Carter","year":"2014","journal-title":"Brief. Bioinf"},{"key":"2023012713441864600_btx809-B11","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/PL00006389","article-title":"Conflict among individual mitochondrial proteins in resolving the phylogeny of eutherian orders","volume":"47","author":"Cao","year":"1998","journal-title":"J. Mol. Evol"},{"key":"2023012713441864600_btx809-B12","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02736122","article-title":"Fast algorithms for the calculation of Kendall\u2019s tau","volume":"20","author":"Christensen","year":"2005","journal-title":"Comput. Stat"},{"key":"2023012713441864600_btx809-B13","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.jtbi.2011.02.005","article-title":"Numerical characteristics of word frequencies and their application to dissimilarity measure for sequence comparison","volume":"276","author":"Dai","year":"2011","journal-title":"J. Theor. Biol"},{"key":"2023012713441864600_btx809-B14","doi-asserted-by":"crossref","first-page":"25.","DOI":"10.1186\/1748-7188-8-25","article-title":"Data compression for sequencing data","volume":"8","author":"Deorowicz","year":"2013","journal-title":"Algorithms Mol. Biol"},{"key":"2023012713441864600_btx809-B15","doi-asserted-by":"crossref","first-page":"e67048.","DOI":"10.1371\/journal.pone.0067048","article-title":"Complete mitochondrial DNA sequences of the threadfin cichlid (Petrochromis trewavasae) and the blunthead cichlid (Tropheus moorii) and patterns of mitochondrial genome evolution in cichlid fishes","volume":"8","author":"Fischer","year":"2013","journal-title":"PLoS One"},{"key":"2023012713441864600_btx809-B16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cosrev.2011.11.001","article-title":"Textual data compression in computational biology: Algorithmic techniques","volume":"6","author":"Giancarlo","year":"2012","journal-title":"Comput. Sci. Rev"},{"key":"2023012713441864600_btx809-B17","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":"2023012713441864600_btx809-B18","doi-asserted-by":"crossref","first-page":"i249","DOI":"10.1093\/bioinformatics\/btm211","article-title":"A statistical method for alignment-free comparison of regulatory sequences","volume":"23","author":"Kantorovitz","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012713441864600_btx809-B19","doi-asserted-by":"crossref","first-page":"5660","DOI":"10.1073\/pnas.80.18.5660","article-title":"New approaches for computer analysis of nucleic acid sequences","volume":"80","author":"Karlin","year":"1983","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012713441864600_btx809-B20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1093\/biomet\/30.1-2.81","article-title":"A new measure of rank correlation","volume":"30","author":"Kendall","year":"1938","journal-title":"Biometrika"},{"key":"2023012713441864600_btx809-B21","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/s00453-013-9859-z","article-title":"Resequencing a set of strings based on a target string","volume":"72","author":"Kuo","year":"2015","journal-title":"Algorithmica"},{"key":"2023012713441864600_btx809-B22","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/j.physa.2004.08.041","article-title":"Relative entropy of DNA and its application","volume":"347","author":"Li","year":"2005","journal-title":"Phys. A Stat. Mech. Appl"},{"key":"2023012713441864600_btx809-B23","first-page":"1128","author":"Lin","year":"2016"},{"key":"2023012713441864600_btx809-B24","author":"Lin","year":"2017"},{"key":"2023012713441864600_btx809-B25","doi-asserted-by":"crossref","first-page":"64.","DOI":"10.1016\/j.ympev.2006.05.019","article-title":"Clustering DNA sequences by feature vectors","volume":"41","author":"Liu","year":"2006","journal-title":"Mol. Phylogenet. Evol"},{"key":"2023012713441864600_btx809-B26","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.jda.2011.01.002","article-title":"On the number of elements to reorder when updating a suffix array","volume":"11","author":"L\u00e9onard","year":"2012","journal-title":"J. Discret. Algorithms"},{"key":"2023012713441864600_btx809-B27","doi-asserted-by":"crossref","first-page":"111.","DOI":"10.1186\/s12864-017-3500-5","article-title":"A program to compute the soft Robinson\u2013Foulds distance between phylogenetic networks","volume":"18","author":"Lu","year":"2017","journal-title":"BMC Genomics"},{"key":"2023012713441864600_btx809-B28","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput"},{"key":"2023012713441864600_btx809-B29","doi-asserted-by":"crossref","first-page":"249.","DOI":"10.2307\/2290477","article-title":"Rank correlation methods (5th ed.)","volume":"87","author":"Marden","year":"1992","journal-title":"J. Am. Stat. Assoc"},{"key":"2023012713441864600_btx809-B30","doi-asserted-by":"crossref","first-page":"2122","DOI":"10.1093\/bioinformatics\/btg295","article-title":"A new sequence distance measure for phylogenetic tree construction","volume":"19","author":"Otu","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012713441864600_btx809-B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00239-003-2493-7","article-title":"Whole proteome prokaryote phylogeny without sequence alignment: a K-string composition approach","volume":"58","author":"Qi","year":"2004","journal-title":"J. Mol. Evol"},{"key":"2023012713441864600_btx809-B32","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1089\/cmb.2009.0198","article-title":"Alignment-free sequence comparison (I): statistics and power","volume":"16","author":"Reinert","year":"2009","journal-title":"J. Comput. Biol"},{"key":"2023012713441864600_btx809-B33","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1093\/oxfordjournals.molbev.a026379","article-title":"Where do rodents fit? Evidence from the complete mitochondrial genome of Sciurus vulgaris","volume":"17","author":"Reyes","year":"2000","journal-title":"Mol. Biol. Evol"},{"key":"2023012713441864600_btx809-B34","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":"2023012713441864600_btx809-B35","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1137\/1006100","article-title":"Normal functions of normal random variables","volume":"6","author":"Shepp","year":"1964","journal-title":"SIAM Rev"},{"key":"2023012713441864600_btx809-B36","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/978-3-642-27866-2_45","volume-title":"Affective Computing and Intelligent Interaction","author":"Shi","year":"2012"},{"key":"2023012713441864600_btx809-B37","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol"},{"key":"2023012713441864600_btx809-B38","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1093\/bib\/bbt067","article-title":"New developments of alignment-free sequence comparison: measures, statistics and next-generation sequencing","volume":"15","author":"Song","year":"2014","journal-title":"Brief. Bioinf"},{"key":"2023012713441864600_btx809-B39","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1093\/bib\/bbt068","article-title":"Information theory applications for biological sequence analysis","volume":"15","author":"Vinga","year":"2014","journal-title":"Brief. Bioinf"},{"key":"2023012713441864600_btx809-B40","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1093\/bioinformatics\/btg005","article-title":"Alignment-free sequence comparison: a review","volume":"19","author":"Vinga","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012713441864600_btx809-B41","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1089\/cmb.2010.0056","article-title":"Alignment-free sequence comparison (II): theoretical power of comparison statistics","volume":"17","author":"Wan","year":"2010","journal-title":"J. Comput. Biol"},{"key":"2023012713441864600_btx809-B42","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1109\/TCBB.2013.122","article-title":"FRESCO: referential compression of highly similar sequences","volume":"10","author":"Wandelt","year":"2013","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023012713441864600_btx809-B43","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.mbs.2008.06.001","article-title":"WSE, a new sequence distance measure based on word frequencies","volume":"215","author":"Wang","year":"2008","journal-title":"Math. Biosci"},{"key":"2023012713441864600_btx809-B44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-13-174","article-title":"A novel hierarchical clustering algorithm for gene sequences","volume":"13","author":"Wei","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023012713441864600_btx809-B45","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1016\/j.ympev.2011.02.020","article-title":"A new distribution vector and its application in genome clustering","volume":"59","author":"Zhao","year":"2011","journal-title":"Mol. Phylogenet. Evol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/10\/1682\/48935761\/bioinformatics_34_10_1682.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/10\/1682\/48935761\/bioinformatics_34_10_1682.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T14:24:05Z","timestamp":1674829445000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/10\/1682\/4747886"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2017,12,15]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx809","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,5,15]]},"published":{"date-parts":[[2017,12,15]]}}}