Digital search trees and chaos game representation

Details Digital search trees and chaos game representation Digital search trees and chaos game representation

2006-05-29

arxiv.org/abs/math/0605719v1

Mathematics

Probability

Scientific paper

In this paper, we consider a possible representation of a DNA sequence in a quaternary tree, in which on can visualize repetitions of subwords. 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 and the insertion depth for DST built from i.i.d. successive sequences. Here, the successive inserted wors are strongly dependent. We give the asymptotic behaviour of the insertion depth and of the length of branches for the CGR-tree obtained from the suffixes of 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.

Affiliated with

Also associated with

No associations

Rating

Digital search trees and chaos game representation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Digital search trees and chaos game representation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital search trees and chaos game representation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-168150