On Suboptimal LCS-alignments for Independent Bernoulli Sequences with Asymmetric Distributions |
| |
Authors: | Stanislaw Barder Jüri Lember Heinrich Matzinger M?rt Toots |
| |
Institution: | 1. University of Bielefeld, Postfach 10 01 31, 33501, Bielefeld, Germany 2. Institute of Mathematical Statistics, University of Tartu, Liivi 2-513, 50409, Tartu, Estonia 3. School of Mathematics, Georgia Tech, Atlanta, GA, 30332-0160, USA
|
| |
Abstract: | Let X = X
1 ... X
n
and Y = Y
1 ... Y
n
be two binary sequences with length n. A common subsequence of X and Y is any subsequence of X that at the same time is a subsequence of Y; The common subsequence with maximal length is called the longest common subsequence (LCS) of X and Y. LCS is a common tool for measuring the closeness of X and Y. In this note, we consider the case when X and Y are both i.i.d. Bernoulli sequences with the parameters ϵ and 1 − ϵ, respectively. Hence, typically the sequences consist of large and short blocks of different colors. This gives an idea to
the so-called block-by-block alignment, where the short blocks in one sequence are matched to the long blocks of the same
color in another sequence. Such and alignment is not necessarily a LCS, but it is computationally easy to obtain and, therefore,
of practical interest. We investigate the asymptotical properties of several block-by-block type of alignments. The paper
ends with the simulation study, where the of block-by-block type of alignments are compared with the LCS. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|