The distribution of shortword match counts between markovian sequences

Conrad J. Burden; Paul Leopardi; Sylvain Forêt

The distribution of shortword match counts between markovian sequences

Conrad J. Burden, Paul Leopardi, Sylvain Forêt

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The D₂ statistic, which counts the number of word matches between two given sequences, has long been proposed as a measure of similarity for biological sequences. Much of the mathematically rigorous work carried out to date on the properties of the D2 statistic has been restricted to the case of 'Bernoulli' sequences composed of identically and independently distributed letters. Here the properties of the distribution of this statistic for the biologically more realistic case of Markovian sequences is studied. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulae for the mean and variance to be derived. The formulae are confirmed using numerical simulations, and asymptotic approximations to the full distribution are tested.

Original language	English
Title of host publication	BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms
Pages	25-33
Number of pages	9
Publication status	Published - 2013
Event	International Conference on Bioinformatics Models, Methods and Algorithms, BIOINFORMATICS 2013 - Barcelona, Spain Duration: 11 Feb 2013 → 14 Feb 2013

Publication series

Name	BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms

Conference

Conference	International Conference on Bioinformatics Models, Methods and Algorithms, BIOINFORMATICS 2013
Country/Territory	Spain
City	Barcelona
Period	11/02/13 → 14/02/13

Cite this

Burden, C. J., Leopardi, P., & Forêt, S. (2013). The distribution of shortword match counts between markovian sequences. In BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms (pp. 25-33). (BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms).

Burden, Conrad J. ; Leopardi, Paul ; Forêt, Sylvain. / The distribution of shortword match counts between markovian sequences. BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms. 2013. pp. 25-33 (BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms).

@inproceedings{655deb24f35c4fd389f79efaabf18ed2,

title = "The distribution of shortword match counts between markovian sequences",

abstract = "The D2 statistic, which counts the number of word matches between two given sequences, has long been proposed as a measure of similarity for biological sequences. Much of the mathematically rigorous work carried out to date on the properties of the D2 statistic has been restricted to the case of 'Bernoulli' sequences composed of identically and independently distributed letters. Here the properties of the distribution of this statistic for the biologically more realistic case of Markovian sequences is studied. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulae for the mean and variance to be derived. The formulae are confirmed using numerical simulations, and asymptotic approximations to the full distribution are tested.",

keywords = "Biological sequence comparison, Word matches",

author = "Burden, {Conrad J.} and Paul Leopardi and Sylvain For{\^e}t",

year = "2013",

language = "English",

isbn = "9789898565358",

series = "BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms",

pages = "25--33",

booktitle = "BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms",

note = "International Conference on Bioinformatics Models, Methods and Algorithms, BIOINFORMATICS 2013 ; Conference date: 11-02-2013 Through 14-02-2013",

}

Burden, CJ , Leopardi, P & Forêt, S 2013, The distribution of shortword match counts between markovian sequences. in BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms. BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms, pp. 25-33, International Conference on Bioinformatics Models, Methods and Algorithms, BIOINFORMATICS 2013, Barcelona, Spain, 11/02/13.

The distribution of shortword match counts between markovian sequences. / Burden, Conrad J.; Leopardi, Paul; Forêt, Sylvain.
BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms. 2013. p. 25-33 (BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The distribution of shortword match counts between markovian sequences

AU - Burden, Conrad J.

AU - Leopardi, Paul

AU - Forêt, Sylvain

PY - 2013

Y1 - 2013

N2 - The D2 statistic, which counts the number of word matches between two given sequences, has long been proposed as a measure of similarity for biological sequences. Much of the mathematically rigorous work carried out to date on the properties of the D2 statistic has been restricted to the case of 'Bernoulli' sequences composed of identically and independently distributed letters. Here the properties of the distribution of this statistic for the biologically more realistic case of Markovian sequences is studied. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulae for the mean and variance to be derived. The formulae are confirmed using numerical simulations, and asymptotic approximations to the full distribution are tested.

AB - The D2 statistic, which counts the number of word matches between two given sequences, has long been proposed as a measure of similarity for biological sequences. Much of the mathematically rigorous work carried out to date on the properties of the D2 statistic has been restricted to the case of 'Bernoulli' sequences composed of identically and independently distributed letters. Here the properties of the distribution of this statistic for the biologically more realistic case of Markovian sequences is studied. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulae for the mean and variance to be derived. The formulae are confirmed using numerical simulations, and asymptotic approximations to the full distribution are tested.

KW - Biological sequence comparison

KW - Word matches

UR - http://www.scopus.com/inward/record.url?scp=84877974186&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9789898565358

T3 - BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms

SP - 25

EP - 33

BT - BIOINFORMATICS 2013 - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms

T2 - International Conference on Bioinformatics Models, Methods and Algorithms, BIOINFORMATICS 2013

Y2 - 11 February 2013 through 14 February 2013

ER -

The distribution of shortword match counts between markovian sequences

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this