The distribution of word matches between Markovian sequences with periodic boundary conditions
Download (720.17 kB)
-
Altmetric Citations
Burden, Conrad J; Leopardi, Paul; Foret, Sylvain
Description
Word match counts have traditionally been proposed as an alignment-free measure of similarity for biological sequences. The D2 statistic, which simply counts the number of exact word matches between two sequences, is a useful test bed for developing rigorous mathematical results, which can then be extended to more biologically useful measures. The distributional properties of the D2 statistic under the null hypothesis of identically and independently distributed letters have been studied...[Show more]
dc.contributor.author | Burden, Conrad J | |
---|---|---|
dc.contributor.author | Leopardi, Paul | |
dc.contributor.author | Foret, Sylvain | |
dc.date.accessioned | 2014-04-09T05:09:09Z | |
dc.date.available | 2014-04-09T05:09:09Z | |
dc.identifier.issn | 1066-5277 | |
dc.identifier.uri | http://hdl.handle.net/1885/11552 | |
dc.description.abstract | Word match counts have traditionally been proposed as an alignment-free measure of similarity for biological sequences. The D2 statistic, which simply counts the number of exact word matches between two sequences, is a useful test bed for developing rigorous mathematical results, which can then be extended to more biologically useful measures. The distributional properties of the D2 statistic under the null hypothesis of identically and independently distributed letters have been studied extensively, but no comprehensive study of the D2 distribution for biologically more realistic higher-order Markovian sequences exists. Here we derive exact formulas for the mean and variance of the D2 statistic for Markovian sequences of any order, and demonstrate through Monte Carlo simulations that the entire distribution is accurately characterized by a Pólya-Aeppli distribution for sequence lengths of biological interest. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulas for the mean and variance to be derived. We also carry out a preliminary comparison between the approximate D2 distribution computed with the theoretical mean and variance under a Markovian hypothesis and an empirical D2 distribution from the human genome. | |
dc.format | 23 pages | |
dc.publisher | Mary Ann Liebert | |
dc.rights | http://www.sherpa.ac.uk/romeo/issn/1066-5277/ | |
dc.source | Journal of Computational Biology 21.1 (2014): 41-63 | |
dc.source.uri | http://online.liebertpub.com/doi/abs/10.1089/cmb.2012.0277 | |
dc.subject | Markov chains | |
dc.subject | sequence analysis | |
dc.subject | statistical models | |
dc.title | The distribution of word matches between Markovian sequences with periodic boundary conditions | |
dc.type | Journal article | |
local.identifier.citationvolume | 21 | |
dc.date.issued | 2014 | |
local.identifier.absfor | 010402 - Biostatistics | |
local.identifier.absfor | 060102 - Bioinformatics | |
local.identifier.ariespublication | f5625xPUB6238 | |
local.publisher.url | http://www.liebertpub.com/ | |
local.type.status | Published Version | |
local.contributor.affiliation | Burden, Conrad J, Mathematical Sciences Institute, Australian National University | |
local.contributor.affiliation | Leopardi, Paul, Mathematical Sciences Institute, Australian National University | |
local.contributor.affiliation | Foret, Sylvain, Research School of Biology, Australian National University | |
dc.relation | http://purl.org/au-research/grants/arc/dp120101422 | |
local.bibliographicCitation.issue | 1 | |
local.bibliographicCitation.startpage | 41 | |
local.bibliographicCitation.lastpage | 63 | |
local.identifier.doi | 10.1089/cmb.2012.0277 | |
local.identifier.absseo | 970101 - Expanding Knowledge in the Mathematical Sciences | |
dc.date.updated | 2015-12-11T09:40:04Z | |
local.identifier.scopusID | 2-s2.0-84891589894 | |
local.identifier.thomsonID | 000329163100003 | |
Collections | ANU Research Publications |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
Burden et al The distribution of word matches 2014.pdf | 720.17 kB | Adobe PDF |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator