{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:26:11Z","timestamp":1773275171457,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"7","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["31171262"],"award-info":[{"award-number":["31171262"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["31428012"],"award-info":[{"award-number":["31428012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["31471246"],"award-info":[{"award-number":["31471246"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["P50 HG 002790"],"award-info":[{"award-number":["P50 HG 002790"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["DMS 1518001"],"award-info":[{"award-number":["DMS 1518001"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["OCE-1136818"],"award-info":[{"award-number":["OCE-1136818"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["EP\/K032402\/1"],"award-info":[{"award-number":["EP\/K032402\/1"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key Basic Research Project of China","award":["2015CB910303"],"award-info":[{"award-number":["2015CB910303"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Next-generation sequencing (NGS) technologies generate large amounts of short read data for many different organisms. The fact that NGS reads are generally short makes it challenging to assemble the reads and reconstruct the original genome sequence. For clustering genomes using such NGS data, word-count based alignment-free sequence comparison is a promising approach, but for this approach, the underlying expected word counts are essential.<\/jats:p>\n               <jats:p>A plausible model for this underlying distribution of word counts is given through modeling the DNA sequence as a Markov chain (MC). For single long sequences, efficient statistics are available to estimate the order of MCs and the transition probability matrix for the sequences. As NGS data do not provide a single long sequence, inference methods on Markovian properties of sequences based on single long sequences cannot be directly used for NGS short read data.<\/jats:p>\n               <jats:p>Results: Here we derive a normal approximation for such word counts. We also show that the traditional Chi-square statistic has an approximate gamma distribution, using the Lander-Waterman model for physical mapping. We propose several methods to estimate the order of the MC based on NGS reads and evaluate those using simulations. We illustrate the applications of our results by clustering genomic sequences of several vertebrate and tree species based on NGS reads using alignment-free sequence dissimilarity measures. We find that the estimated order of the MC has a considerable effect on the clustering results, and that the clustering results that use an MC of the estimated order give a plausible clustering of the species.<\/jats:p>\n               <jats:p>Availability and implementation: Our implementation of the statistics developed here is available as R package \u2018NGS.MC\u2019 at http:\/\/www-rcf.usc.edu\/\u223cfsun\/Programs\/NGS-MC\/NGS-MC.html.<\/jats:p>\n               <jats:p>Contact: \u00a0fsun@usc.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv395","type":"journal-article","created":{"date-parts":[[2015,7,1]],"date-time":"2015-07-01T01:55:14Z","timestamp":1435715714000},"page":"993-1000","source":"Crossref","is-referenced-by-count":23,"title":["Inference of Markovian properties of molecular sequences from NGS data and applications to comparative genomics"],"prefix":"10.1093","volume":"32","author":[{"given":"Jie","family":"Ren","sequence":"first","affiliation":[{"name":"1 Molecular and Computational Biology Program, University of Southern California, Los Angeles, CA, USA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Song","sequence":"additional","affiliation":[{"name":"2 School of Mathematical Sciences, Peking University, Beijing, China,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghua","family":"Deng","sequence":"additional","affiliation":[{"name":"2 School of Mathematical Sciences, Peking University, Beijing, China,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gesine","family":"Reinert","sequence":"additional","affiliation":[{"name":"3 Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles H.","family":"Cannon","sequence":"additional","affiliation":[{"name":"4 Department of Biological Sciences, Texas Tech University, TX 79409-3131, USA,"},{"name":"5 Xishuangbanna Tropical Botanic Garden, Chinese Academy of Sciences, Yunnan, China and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fengzhu","family":"Sun","sequence":"additional","affiliation":[{"name":"1 Molecular and Computational Biology Program, University of Southern California, Los Angeles, CA, USA,"},{"name":"6 Centre for Computational Systems Biology, School of Mathematical Sciences, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"2023020201172930200_btv395-B1","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/0022-5193(83)90251-5","article-title":"A Markov analysis of DNA sequences","volume":"104","author":"Almagor","year":"1983","journal-title":"J. Theor. Biol."},{"key":"2023020201172930200_btv395-B2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1214\/aoms\/1177707039","article-title":"Statistical inference about Markov chains","volume":"28","author":"Anderson","year":"1957","journal-title":"Ann. Math. Stat."},{"key":"2023020201172930200_btv395-B3","doi-asserted-by":"crossref","first-page":"7145","DOI":"10.1093\/nar\/16.14.7145","article-title":"Mono-through hexanucleotide composition of the sense strand of yeast DNA: a Markov chain analysis","volume":"16","author":"Arnold","year":"1988","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF02101152","article-title":"The analysis of intron data and their use in the detection of short signals","volume":"26","author":"Avery","year":"1987","journal-title":"J. Mol. Evol."},{"key":"2023020201172930200_btv395-B5","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1111\/1467-9876.00139","article-title":"Fitting Markov chain models to discrete state series such as DNA sequences","volume":"48","author":"Avery","year":"1999","journal-title":"J. R. Stat. Soc. Ser. C Appl. Stat."},{"key":"2023020201172930200_btv395-B6","doi-asserted-by":"crossref","first-page":"1554","DOI":"10.1214\/aoms\/1177699147","article-title":"Statistical inference for probabilistic functions of finite state Markov chains","volume":"37","author":"Baum","year":"1966","journal-title":"Ann. Math. Stat."},{"key":"2023020201172930200_btv395-B7","doi-asserted-by":"crossref","first-page":"2949","DOI":"10.1093\/bioinformatics\/btu405","article-title":"The amordad database engine for metagenomics","volume":"30","author":"Behnam","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020201172930200_btv395-B8","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1089\/cmb.2012.0280","article-title":"A geometric interpretation for local alignment-free sequence comparison","volume":"20","author":"Behnam","year":"2013","journal-title":"J. Comput. Biol."},{"key":"2023020201172930200_btv395-B9","doi-asserted-by":"crossref","first-page":"e72","DOI":"10.1093\/nar\/gks001","article-title":"Summarizing and correcting the gc content bias in high-throughput sequencing","volume":"40","author":"Benjamini","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B10","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1111\/biom.12009","article-title":"Exact goodness-of-fit tests for Markov chains","volume":"69","author":"Besag","year":"2013","journal-title":"Biometrics"},{"key":"2023020201172930200_btv395-B11","volume-title":"Statistical Inference for Markov Processes","author":"Billingsley","year":"1961"},{"key":"2023020201172930200_btv395-B12","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1214\/aoms\/1177705136","article-title":"Statistical methods in Markov chains","volume":"32","author":"Billingsley","year":"1961","journal-title":"Ann. Math. Stat."},{"key":"2023020201172930200_btv395-B13","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1007\/BF02102360","article-title":"Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucaryotic nuclear DNA sequences both protein-coding and noncoding","volume":"21","author":"Blaisdell","year":"1985","journal-title":"J. Mol. Evol."},{"key":"2023020201172930200_btv395-B14","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1038\/ng.650","article-title":"Chip-seq identification of weakly conserved heart enhancers","volume":"42","author":"Blow","year":"2010","journal-title":"Nat. Genet."},{"key":"2023020201172930200_btv395-B15","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1111\/j.1365-294X.2009.04484.x","article-title":"Assembly free comparative genomics of short-read sequence data discovers the needles in the haystack","volume":"19","author":"Cannon","year":"2010","journal-title":"Mol. Ecol."},{"key":"2023020201172930200_btv395-B16","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1038\/nmeth.2375","article-title":"Predicting the molecular complexity of sequencing libraries","volume":"10","author":"Daley","year":"2013","journal-title":"Nat. Methods"},{"key":"2023020201172930200_btv395-B17","doi-asserted-by":"crossref","DOI":"10.1007\/b137845","volume-title":"Statistical Methods in Bioinformatics: An Introduction","author":"Ewens","year":"2005","edition":"2nd edn"},{"key":"2023020201172930200_btv395-B18","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":"2023020201172930200_btv395-B19","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1093\/biomet\/41.3-4.430","article-title":"A test for Markov chains","volume":"41","author":"Hoel","year":"1954","journal-title":"Biometrika"},{"key":"2023020201172930200_btv395-B20","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.1093\/nar\/18.6.1625","article-title":"Prediction of oligonucleotide frequencies based upon dinucleotide frequencies obtained from the nearest neighbor analysis","volume":"18","author":"Hong","year":"1990","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B21","doi-asserted-by":"crossref","first-page":"10714","DOI":"10.1073\/pnas.1319778111","article-title":"Modeling ecological drivers in marine viral communities using comparative metagenomics and network analyses","volume":"111","author":"Hurwitz","year":"2014","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023020201172930200_btv395-B22","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1186\/1471-2164-13-730","article-title":"Comparison of metagenomic samples using sequence signatures","volume":"13","author":"Jiang","year":"2012","journal-title":"BMC Genomics"},{"key":"2023020201172930200_btv395-B23","doi-asserted-by":"crossref","first-page":"D773","DOI":"10.1093\/nar\/gkm966","article-title":"The UCSC genome browser database: 2008 update","volume":"36","author":"Karolchik","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B24","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0888-7543(88)90007-9","article-title":"Genomic mapping by fingerprinting random clones: a mathematical analysis","volume":"2","author":"Lander","year":"1988","journal-title":"Genomics"},{"key":"2023020201172930200_btv395-B25","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.jtbi.2011.06.020","article-title":"New powerful statistics for alignment-free sequence comparison under a pattern transfer model","volume":"284","author":"Liu","year":"2011","journal-title":"J. Theor. Biol."},{"key":"2023020201172930200_btv395-B26","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1101\/gr.6761107","article-title":"28-way vertebrate alignment and conservation track in the UCSC genome browser","volume":"17","author":"Miller","year":"2007","journal-title":"Genome Res."},{"key":"2023020201172930200_btv395-B27","doi-asserted-by":"crossref","first-page":"1416","DOI":"10.1093\/nar\/gks1285","article-title":"One size does not fit all: On how Markov model order dictates performance of genomic sequence analyses","volume":"41","author":"Narlikar","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B28","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1080\/07391102.1989.10506528","article-title":"Linguistics of nucleotide sequences I: the significance of deviations from mean statistical characteristics and prediction of the frequencies of occurrence of words","volume":"6","author":"Pevzner","year":"1989","journal-title":"J. Biomol. Struct. Dynam."},{"key":"2023020201172930200_btv395-B29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/10665270050081360","article-title":"Probabilistic and statistical properties of words: an overview","volume":"7","author":"Reinert","year":"2000","journal-title":"J. Comput. Biol."},{"key":"2023020201172930200_btv395-B30","first-page":"268","article-title":"Statistics on words with applications to biological sequences","volume-title":"Lothaire: Applied Combinatorics on Words","author":"Reinert","year":"2005"},{"key":"2023020201172930200_btv395-B31","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":"2023020201172930200_btv395-B32","doi-asserted-by":"crossref","first-page":"2690","DOI":"10.1093\/bioinformatics\/btt462","article-title":"Multiple alignment-free sequence comparison","volume":"29","author":"Ren","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020201172930200_btv395-B33","doi-asserted-by":"crossref","first-page":"e3373","DOI":"10.1371\/journal.pone.0003373","article-title":"MetaSim: a sequencing simulator for genomics and metagenomics","volume":"3","author":"Richter","year":"2008","journal-title":"PLoS One"},{"key":"2023020201172930200_btv395-B34","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1093\/bioinformatics\/btu023","article-title":"Exploring genome characteristics and sequence quality without a reference","volume":"30","author":"Simpson","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020201172930200_btv395-B35","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":"2023020201172930200_btv395-B36","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. Bioinformatics"},{"key":"2023020201172930200_btv395-B37","doi-asserted-by":"crossref","first-page":"e84348","DOI":"10.1371\/journal.pone.0084348","article-title":"Comparison of metatranscriptomic samples based on k-tuple frequencies","volume":"9","author":"Wang","year":"2014","journal-title":"PLoS One"},{"key":"2023020201172930200_btv395-B38","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology: Maps, Sequences and Genomes. Chapman & Hall\/CRC Interdisciplinary Statistics","author":"Waterman","year":"1995"},{"key":"2023020201172930200_btv395-B39","doi-asserted-by":"crossref","first-page":"e75","DOI":"10.1093\/nar\/gkt003","article-title":"Co-phylog: an assembly-free phylogenomic approach for closely related organisms","volume":"41","author":"Yi","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023020201172930200_btv395-B40","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1089\/cmb.2012.0029","article-title":"Normal and compound poisson approximations for pattern occurrences in ngs reads","volume":"19","author":"Zhai","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023020201172930200_btv395-B41","doi-asserted-by":"crossref","first-page":"e1000158","DOI":"10.1371\/journal.pcbi.1000158","article-title":"Modeling chip sequencing in silico with applications","volume":"4","author":"Zhang","year":"2008","journal-title":"PLoS Comput. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/7\/993\/49018311\/bioinformatics_32_7_993.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/7\/993\/49018311\/bioinformatics_32_7_993.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T03:36:22Z","timestamp":1675308982000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/7\/993\/2240327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":41,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2016,4,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv395","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,4,1]]},"published":{"date-parts":[[2015,6,30]]}}}