On Suboptimal LCS-alignments for Independent Bernoulli Sequences with Asymmetric Distributions

Stanislaw Barder, Jüri Lember (), Heinrich Matzinger () and Märt Toots
Additional contact information
Stanislaw Barder: University of Bielefeld
Jüri Lember: University of Tartu
Heinrich Matzinger: Georgia Tech
Märt Toots: University of Tartu

Methodology and Computing in Applied Probability, 2012, vol. 14, issue 2, 357-382

Abstract: 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: Longest common subsequence; Suboptimal alignment; Large deviation inequality; 60F10; 60C05 (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-010-9206-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:14:y:2012:i:2:d:10.1007_s11009-010-9206-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-010-9206-7

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().