The distribution of word matches between Markovian sequences with periodic boundary conditions.

ABSTRACT: Word match counts have traditionally been proposed as an alignment-free measure of similarity for biological sequences. The D(2) 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 D(2) statistic under the null hypothesis of identically and independently distributed letters have been studied extensively, but no comprehensive study of the D(2) distribution for biologically more realistic higher-order Markovian sequences exists. Here we derive exact formulas for the mean and variance of the D(2) statistic for Markovian sequences of any order, and demonstrate through Monte Carlo simulations t

SUBMITTER: Burden CJ 

PROVIDER: S-EPMC3880068 | biostudies-literature | 2014 Jan

REPOSITORIES: biostudies-literature