Sparse long blocks and the variance of the LCS

Details Sparse long blocks and the variance of the LCS Sparse long blocks and the variance of the LCS

2012-04-04

arxiv.org/abs/1204.1009v1

Mathematics

Probability

Scientific paper

Consider two random strings having the same length and generated by two mutually independent iid sequences taking values uniformly in a common finite alphabet. We study the order of the variance of the longest common subsequence (LCS) of these strings when long blocks, or other types of atypical substrings, are sparsely added into one of them. We show that the existence of the derivative of the mean LCS-curve at its maximum implies that this order is linear in the length of the strings. We also argue that our proofs carry over to many models used by computational biologists to simulate DNA-sequences.

Affiliated with

Also associated with

No associations

Rating

Sparse long blocks and the variance of the LCS 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 Sparse long blocks and the variance of the LCS, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse long blocks and the variance of the LCS will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32668