Closeness to the Diagonal for Longest Common Subsequences

Details Closeness to the Diagonal for Longest Common Subsequences Closeness to the Diagonal for Longest Common Subsequences

2009-11-10

arxiv.org/abs/0911.2031v2

Mathematics

Probability

Scientific paper

We investigate the nature of the alignment with gaps corresponding to a longest common subsequence (LCS) of two iid random sequences drawn from a ?nite al- phabet. We show that such an alignment, which we call optimal, typically matches pieces of similar length. This is of importance in order to understand the structure of optimal alignments of two sequences. Moreoever we also show that a property, common to two subsequences, typically holds in most parts of the optimal align- ment whenever this same property has a high probability of holding for strings of similar short length. Our results should, in particular, prove useful for simulations. Indeed they imply that the rescaled two dimensional representation of the LCS gets uniformly close to the diagonal as the length of the sequences grows without bound

Affiliated with

Also associated with

No associations

Rating

Closeness to the Diagonal for Longest Common Subsequences 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 Closeness to the Diagonal for Longest Common Subsequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Closeness to the Diagonal for Longest Common Subsequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532820