Geodesic
Digital search trees and chaos game representation
ESAIM: Probability and Statistics, Tome 13 (2009), pp. 15-37

Voir la notice de l'article provenant de la source Numdam

In this paper, we consider a possible representation of a DNA sequence in a quaternary tree, in which one can visualize repetitions of subwords (seen as suffixes of subsequences). The CGR-tree turns a sequence of letters into a Digital Search Tree (DST), obtained from the suffixes of the reversed sequence. Several results are known concerning the height, the insertion depth for DST built from independent successive random sequences having the same distribution. Here the successive inserted words are strongly dependent. We give the asymptotic behaviour of the insertion depth and the length of branches for the CGR-tree obtained from the suffixes of a reversed i.i.d. or markovian sequence. This behaviour turns out to be at first order the same one as in the case of independent words. As a by-product, asymptotic results on the length of longest runs in a markovian sequence are obtained.

DOI : 10.1051/ps:2007043
Classification : 60C05, 68R15, 92D20, 05D40
Keywords: random tree, digital search tree, CGR, lengths of the paths, height, insertion depth, asymptotic growth, strong convergence 
@article{PS_2009__13__15_0,
     author = {C\'enac, Peggy and Chauvin, Brigitte and Ginouillac, St\'ephane and Pouyanne, Nicolas},
     title = {Digital search trees and chaos game representation},
     journal = {ESAIM: Probability and Statistics},
     pages = {15--37},
     publisher = {EDP-Sciences},
     volume = {13},
     year = {2009},
     doi = {10.1051/ps:2007043},
     mrnumber = {2493853},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ps:2007043/}
}
TY  - JOUR
AU  - Cénac, Peggy
AU  - Chauvin, Brigitte
AU  - Ginouillac, Stéphane
AU  - Pouyanne, Nicolas
TI  - Digital search trees and chaos game representation
JO  - ESAIM: Probability and Statistics
PY  - 2009
SP  - 15
EP  - 37
VL  - 13
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ps:2007043/
DO  - 10.1051/ps:2007043
LA  - en
ID  - PS_2009__13__15_0
ER  - 
%0 Journal Article
%A Cénac, Peggy
%A Chauvin, Brigitte
%A Ginouillac, Stéphane
%A Pouyanne, Nicolas
%T Digital search trees and chaos game representation
%J ESAIM: Probability and Statistics
%D 2009
%P 15-37
%V 13
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ps:2007043/
%R 10.1051/ps:2007043
%G en
%F PS_2009__13__15_0
Cénac, Peggy; Chauvin, Brigitte; Ginouillac, Stéphane; Pouyanne, Nicolas. Digital search trees and chaos game representation. ESAIM: Probability and Statistics, Tome 13 (2009), pp. 15-37. doi: 10.1051/ps:2007043

Cité par Sources :