{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:26:28Z","timestamp":1773275188015,"version":"3.50.1"},"reference-count":35,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Analyses of genomic signatures are gaining attention as they allow studies of species-specific relationships without involving alignments of homologous sequences. A na\u00efve Bayesian classifier was built to discriminate between different bacterial compositions of short oligomers, also known as DNA words. The classifier has proven successful in identifying foreign genes in Neisseria meningitis. In this study we extend the classifier approach using either a fixed higher order Markov model (Mk) or a variable length Markov model (VLMk).<\/jats:p>\n               <jats:p>Results: We propose a simple algorithm to lock a variable length Markov model to a certain number of parameters and show that the use of Markov models greatly increases the flexibility and accuracy in prediction to that of a na\u00efve model. We also test the integrity of classifiers in terms of false-negatives and give estimates of the minimal sizes of training data. We end the report by proposing a method to reject a false hypothesis of horizontal gene transfer.<\/jats:p>\n               <jats:p>Availability: Software and Supplementary information available at<\/jats:p>\n               <jats:p>Contact: \u00a0dalevi@cs.chalmers.se<\/jats:p>","DOI":"10.1093\/bioinformatics\/btk029","type":"journal-article","created":{"date-parts":[[2006,1,11]],"date-time":"2006-01-11T01:18:22Z","timestamp":1136942302000},"page":"517-522","source":"Crossref","is-referenced-by-count":23,"title":["Bayesian classifiers for detecting HGT using fixed and variable order markov models of genomic signatures"],"prefix":"10.1093","volume":"22","author":[{"given":"Daniel","family":"Dalevi","sequence":"first","affiliation":[{"name":"Department of Computing Science, Chalmers University 1 \u00a0 1 \u00a0 \u00a0 SE 412 96 G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devdatt","family":"Dubhashi","sequence":"additional","affiliation":[{"name":"Department of Computing Science, Chalmers University 1 \u00a0 1 \u00a0 \u00a0 SE 412 96 G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malte","family":"Hermansson","sequence":"additional","affiliation":[{"name":"Department of Cell and Molecular Biology, Microbiology, G\u00f6teborg University 2 \u00a0 2 \u00a0 \u00a0 405 30 G\u00f6teborg, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2006,1,10]]},"reference":[{"key":"2023012408521453800_b1","doi-asserted-by":"crossref","first-page":"425","DOI":"10.18388\/abp.2003_3696","article-title":"Spread and survival of promiscuous IncP-1 plasmids","volume":"50","author":"Adamczyk","year":"2003","journal-title":"Acta Biochim. Pol."},{"key":"2023012408521453800_b2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0303-2647(93)90068-N","article-title":"Recognition of genes in DNA sequence with ambiguities","volume":"30","author":"Borodovsky","year":"1993","journal-title":"Biosystems"},{"key":"2023012408521453800_b3","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1214\/aos\/1018031204","article-title":"Variable length Markov chains","volume":"27","author":"B\u00fchlmann","year":"1999","journal-title":"Ann. Statist."},{"key":"2023012408521453800_b4","doi-asserted-by":"crossref","first-page":"1358","DOI":"10.1073\/pnas.89.4.1358","article-title":"Over- and under-representation of short oligonucleotides in DNA sequences","volume":"89","author":"Burge","year":"1992","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408521453800_b5","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/s00239-001-0087-9","article-title":"Measuring genome divergence in bacteria: a case study using chlamydian","volume":"55","author":"Dalevi","year":"2002","journal-title":"J. Mol. Evol."},{"key":"2023012408521453800_b6","doi-asserted-by":"crossref","first-page":"2124","DOI":"10.1126\/science.284.5423.2124","article-title":"Phylogenetic classification and the universal tree","volume":"284","author":"Doolittle","year":"1999","journal-title":"Science"},{"key":"2023012408521453800_b7","doi-asserted-by":"crossref","first-page":"e6","DOI":"10.1093\/nar\/gni004","article-title":"Detection and characterization of horizontal transfers in prokaryotes genomic signature","volume":"33","author":"Dufraigne","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012408521453800_b8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids.","author":"Durbin","year":"1998"},{"key":"2023012408521453800_b9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1093\/biomet\/72.1.45","article-title":"Bootstrap confidence intervals for a class of parametric problems","volume":"72","author":"Efron","year":"1985","journal-title":"Biometrika"},{"key":"2023012408521453800_b10","doi-asserted-by":"crossref","first-page":"s100","DOI":"10.1093\/bioinformatics\/18.suppl_2.S100","article-title":"Identifying transcription factor binding sites through Markov chain","volume":"18","author":"Ellrott","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012408521453800_b11","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0378-1119(00)00472-8","article-title":"Chargaff's legacy","volume":"261","author":"Forsdyke","year":"2000","journal-title":"Gene"},{"key":"2023012408521453800_b12","first-page":"138","article-title":"New Algorithms for the Duplication-Loss Model","volume-title":"Proceedings of the Research on Computational Molecular Biology.","author":"Hallet","year":"2000"},{"key":"2023012408521453800_b13","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00239-001-0051-8","article-title":"Detection of genes with atypical nucleotide sequence in microbial genomes","volume":"54","author":"Hooper","year":"2002","journal-title":"J. Mol. Evol."},{"key":"2023012408521453800_b14","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0168-9525(00)89076-9","article-title":"Dinucleotide relative abundance extremes: a genomic signature","volume":"11","author":"Karlin","year":"1995","journal-title":"Trends Genet."},{"key":"2023012408521453800_b15","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1093\/oxfordjournals.molbev.a003816","article-title":"Codon bias and base composition are poor indicators of horizontally transferred genes","volume":"18","author":"Koski","year":"2001","journal-title":"Mol. Biol. Evol."},{"key":"2023012408521453800_b16","doi-asserted-by":"crossref","first-page":"12381","DOI":"10.1073\/pnas.95.21.12381","article-title":"Natural genetic exchange between Haemophilus and Neisseria: intergeneric of chromosomal genes between major human pathogens","volume":"95","author":"Kroll","year":"1998","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408521453800_b17","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/PL00006158","article-title":"Amelioration of bacterial genomes: rates of change and exchange","volume":"44","author":"Lawrence","year":"1997","journal-title":"J. Mol. Evol."},{"key":"2023012408521453800_b18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.2165\/00822942-200403040-00003","article-title":"Genomic conflict settled in favour of the species rather than the gene at GC percentage values","volume":"3","author":"Lee","year":"2004","journal-title":"Appl. Bioinformatics"},{"key":"2023012408521453800_b19","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1198\/1061860043524","article-title":"Variable Length Markov chains: methodology, computing, and software","volume":"13","author":"M\u00e4chler","year":"2004","journal-title":"J. Comp. Graph. Stat."},{"key":"2023012408521453800_b20","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1073\/pnas.84.1.166","article-title":"The guanine and cytosine content of genomic DNA and bacterial evolution","volume":"84","author":"Muto","year":"1987","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408521453800_b21","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1038\/ng1381","article-title":"Biased biological functions of horizontally transferred genes in genomes [Erratum (2004) Nat. Genet., 36 1126.]","volume":"36","author":"Nakamura","year":"2004","journal-title":"Nat. Genet."},{"key":"2023012408521453800_b22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1101\/gr.335003","article-title":"Evolutionary implications of microbial genome tetranucleotide frequency","volume":"13","author":"Pride","year":"2003","journal-title":"Genome Res."},{"key":"2023012408521453800_b23","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":"2023012408521453800_b24","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1023\/A:1026490906255","article-title":"The power of amnesia: learning probabilistic automata with variable memory length","volume":"25","author":"Ron","year":"1996","journal-title":"Mach. Learn."},{"key":"2023012408521453800_b25","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1093\/nar\/26.2.544","article-title":"Microbial gene identification using interpolated Markov models","volume":"26","author":"Salzberg","year":"1998","journal-title":"Nucleic Acids Res."},{"key":"2023012408521453800_b26","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1101\/gr.186401","article-title":"Capturing whole-genome characteristics in short sequences using a naive classifier","volume":"11","author":"Sandberg","year":"2001","journal-title":"Genome Res."},{"key":"2023012408521453800_b27","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0378-1119(03)00581-X","article-title":"Quantifying the species-specificity in genomic signatures, synonymous codon choice, amino acid usage and G+C content","volume":"311","author":"Sandberg","year":"2003","journal-title":"Gene"},{"key":"2023012408521453800_b28","doi-asserted-by":"crossref","first-page":"7134","DOI":"10.1073\/pnas.91.15.7134","article-title":"Atypical regions in large genomic DNA sequences","volume":"91","author":"Scherer","year":"1994","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408521453800_b29","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/0959-437X(94)90070-1","article-title":"Codon usage and genome evolution","volume":"4","author":"Sharp","year":"1994","journal-title":"Curr. Opin. Genet. Dev."},{"key":"2023012408521453800_b30","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1093\/nar\/29.2.545","article-title":"A phylogenomic approach to microbial evolution","volume":"29","author":"Sicheritz-Ponten","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012408521453800_b31","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1111\/j.1462-2920.2004.00624.x","article-title":"Application of tetranucleotide frequencies for the assignment of genomic","volume":"6","author":"Teeling","year":"2004","journal-title":"Environ. Microbiol."},{"key":"2023012408521453800_b32","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.gene.2004.10.021","article-title":"The spectrum of genomic signatures: from dinucleotides to chaos game","volume":"346","author":"Wang","year":"2005","journal-title":"Gene"},{"key":"2023012408521453800_b33","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1006\/jmbi.1996.0261","article-title":"Distribution of restriction enzyme recognition sequences on broad host range plasmid RP4: molecular and evolutionary implications","volume":"258","author":"Wilkins","year":"1996","journal-title":"J. Mol. Biol."},{"key":"2023012408521453800_b34","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1128\/mr.51.2.221-271.1987","article-title":"Bacterial evolution","volume":"51","author":"Woese","year":"1987","journal-title":"Microbiol. Rev."},{"key":"2023012408521453800_b35","first-page":"68","article-title":"Finding short DNA motifs using permuted Markov models","volume-title":"Proceedings of the Research on Computational molecular Biology.","author":"Zhao","year":"2004"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/5\/517\/48838639\/bioinformatics_22_5_517.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/5\/517\/48838639\/bioinformatics_22_5_517.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T09:29:21Z","timestamp":1674552561000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/5\/517\/206170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,10]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btk029","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,3,1]]},"published":{"date-parts":[[2006,1,10]]}}}