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

Znamenskij Sergej Vitalevich; Знаменский Сергей Витальевич

Scientific articles \ Mathematics. Natural sciences \ Mathematics \ Probability. Mathematical statistics

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

Znamenskij Sergej Vitalevich

Journal: Программные системы: теория и приложения @programmnye-sistemy

Section: Математические основы программирования

Article in issue: 1 (28) т.7, 2016.

Free access

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 and 𝑛; Exact probability distributions tables are presented for all couples of length in a range 2

lcs \ levenshtein metric \ edit distance \ sequence alignment \ similarity of strings

Similar articles in the section Probability. Mathematical statistics

Об одном парадоксе закона больших чисел для максимальных серий в последовательной выборке

Плотников А.Н.

Закон распределения длины максимальной серии и его статистические приложения

Плотников А.Н.

О критерии проверки вложения с допуском для дискретных последовательностей

Меженная Наталья Михайловна

О распределении чисел пар и троек одинаковых знаков на цикле двоичной мультициклической последовательности

Меженная Наталья Михайловна

Locating All Common Subsequences in Two DNA Sequences

M. I. Khalil

Finding Longest Common Substrings in Documents

M.I.Khalil, M.A.Hadi

Short address: https://sciup.org/14336063

IDS: 14336063

Картина наибольшей длины общих подпоследовательностей пары случайных строк 4 буквенного алфавита

Наибольшая длина (LCS) общей подпоследовательности пары случайных конечных последовательностей из 4 букв рассмотрена как случайная функция от длин и этих двух последовательностей. Представлены таблицы точных значений вероятностей для всех пар конкретных длин в диапазоне 2

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

Durbin R., Eddy S., Krogh A., Mitchison G. Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998, 356 с.
J. G. Reich, H. Drabsch, A. D¨ aumler, On the statistical assessment of similarities in DNA sequences. Nucleic acids research, 12(13), 5529-5543.1984..
K. Ning, K. P. Choi. Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences arXiv preprint arXiv:1306.4253//2013.
V. Chvatal, D. Sankoff. Longest Common subsequences of two random sequences//J. Appl. Probability, 1975, №12. С. 306-315.
R. Bundschuh. High precision simulations of the longest common subsequence problem//The European Physical Journal B-Condensed Matter and Complex Systems, V. 22. No. 4. 2001. С. 533-541.