RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Program Systems: Theory and Applications:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Program Systems: Theory and Applications, 2016, Volume 7, Issue 1, Pages 201–208 (Mi ps207)  

This article is cited in 2 scientific papers (total in 2 papers)

Mathematical Foundations of Programming

A picture of common subsequence length for two random strings over an alphabet of 4 symbols

S. V. Znamenskij

Ailamazyan Program System Institute of RAS

Abstract: The maximal length of longest common subsequence (LCS) for a couple of random finite sequences over an alphabet of 4 characters was considered as a random function of the sequences lengths $m$ and $n$. Exact probability distributions tables are presented for all couples of length in a range $2<m+n<19$.
The graphs of expected value and standard deviation as a functions of length are shown in linear perspective which presents the behaviour of large lengths at the horizon. In order to illustrate behaviour on large lengths, the results of numeric simulation for $m+n=32$, 512, 8192 and 131072 are also shown on the same graphs. The presented graph of expected value dependency of $m$ and $n$ looks to have asymptotic right circular cone. The variance looks alike growing as $(n+m)^{\frac34}$.

Key words and phrases: similarity of strings, sequence alignment, edit distance, LCS, Levenshtein metric.

Full text: PDF file (1200 kB)
References: PDF file   HTML file

Document Type: Article
UDC: 004.416
Received: 25.12.2015
Accepted: 28.03.2016
Language: English

Citation: S. V. Znamenskij, “A picture of common subsequence length for two random strings over an alphabet of 4 symbols”, Program Systems: Theory and Applications, 7:1 (2016), 201–208

Citation in format AMSBIB
\Bibitem{Zna16}
\by S.~V.~Znamenskij
\paper A picture of common subsequence length for two random strings over an alphabet of 4 symbols
\jour Program Systems: Theory and Applications
\yr 2016
\vol 7
\issue 1
\pages 201--208
\mathnet{http://mi.mathnet.ru/ps207}


Linking options:
  • http://mi.mathnet.ru/eng/ps207
  • http://mi.mathnet.ru/eng/ps/v7/i1/p201

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. S. V. Znamenskii, “Priblizhenie dliny naibolshei obschei podposledovatelnosti pary sluchainykh strok”, Programmnye sistemy: teoriya i prilozheniya, 7:4 (2016), 347–358  mathnet
    2. Sergej V. Znamenskij, “A formula for the mean length of the longest common subsequence”, Zhurn. SFU. Ser. Matem. i fiz., 10:1 (2017), 71–74  mathnet  crossref
  • Program Systems: Theory and Applications
    Number of views:
    This page:63
    Full text:15
    References:14

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019