A characterization of the number of subsequences obtained via the deletion channel

Details A characterization of the number of subsequences obtained via the deletion channel A characterization of the number of subsequences obtained via the deletion channel

2012-02-08

arxiv.org/abs/1202.1644v1

Computer Science

Information Theory

9 pages, 4 figures, a short version submitted to ISIT2012

Scientific paper

Motivated by the study of deletion channels, this work presents improved bounds on the number of subsequences obtained from a binary sting X of length n under t deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string X; where a run is a maximal sequence of the same character. Our improved bounds are obtained by a structural analysis of the family of r-run strings X, an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every r, we present r-run strings with the minimum (respectively maximum) number of subsequences under any t deletions; and perform an exact analysis of the number of subsequences of these extremal strings.

Affiliated with

Also associated with

No associations

Rating

A characterization of the number of subsequences obtained via the deletion channel 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 A characterization of the number of subsequences obtained via the deletion channel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A characterization of the number of subsequences obtained via the deletion channel will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-64308