Константы Хватала – Санкова. - Chvátal–Sankoff constants

В математика, то Константы Хватала – Санкова. находятся математические константы которые описывают длину самые длинные общие подпоследовательности из случайный струны. Хотя существование этих констант было доказано, их точные значения неизвестны. Они названы в честь Вацлав Хваталь и Дэвид Санкофф, которые начали исследовать их в середине 1970-х годов.^[1][2]

Есть одна постоянная Хватала – Санкоффа ${\displaystyle \gamma _{k}}$ для каждого положительного целого числа k, куда k - это количество символов в алфавите, из которого берутся случайные строки. Последовательность этих чисел растет обратно пропорционально квадратному корню из k.^[3] Однако некоторые авторы пишут «постоянную Хватала – Санкоффа» для обозначения ${\displaystyle \gamma _{2}}$, константа, определенная таким образом для двоичного алфавита.^[4]

Фон

Обычная подпоследовательность из двух строк S и Т это строка, символы которой появляются в одном и том же порядке (не обязательно последовательно) как в S И в Т. Проблема вычисления самая длинная общая подпоследовательность хорошо изучена в области информатики. Это можно решить в полиномиальное время к динамическое программирование;^[5] этот базовый алгоритм имеет дополнительные ускорения для малых алфавитов ( Метод четырех русских ),^[6] для струн с небольшими отличиями,^[7] для строк с несколькими совпадающими парами символов,^[8] и т.д. Эта проблема и ее обобщения на более сложные формы редактировать расстояние имеют важные приложения в областях, которые включают биоинформатика (в сравнении ДНК и белковые последовательности и реконструкция эволюционные деревья ), геология (в стратиграфия ), и Информатика (в сравнение данных и контроль версий ).^[7]

Одна из причин изучения самых длинных общих подпоследовательностей случайных строк, которую уже давали Хватал и Санкофф, состоит в том, чтобы откалибровать вычисления самых длинных общих подпоследовательностей на строках, которые не являются случайными. Если такое вычисление возвращает подпоследовательность, которая значительно длиннее, чем то, что было бы получено случайным образом, из этого результата можно сделать вывод, что совпадение является значимым или значимым.^[1]

Определение и существование

Константы Хватала – Санкова описывают поведение следующего случайного процесса. Данные параметры п и k, выберите две длинып струны S и Т из того же k-символьный алфавит, каждый символ каждой выбранной строки равномерно случайно, независимо от всех остальных персонажей. Вычислите самую длинную общую подпоследовательность этих двух строк, и пусть ${\displaystyle \lambda _{n,k}}$ быть случайная переменная значение которой является длиной этой подпоследовательности. Тогда ожидаемое значение из ${\displaystyle \lambda _{n,k}}$ (с точностью до членов более низкого порядка) пропорциональноп, а kth постоянная Хватала – Санкоффа ${\displaystyle \gamma _{k}}$ это константа пропорциональности.^[2]

Точнее, ожидаемое значение ${\displaystyle E[\lambda _{n,k}]}$ является супераддитив: для всех м и п, ${\displaystyle E[\lambda _{m+n,k}]\geq E[\lambda _{m,k}]+E[\lambda _{n,k}]}$. Это потому, что если строки длины м + п разбиты на подстроки длины м и п, и найдены самые длинные общие подпоследовательности этих подстрок, они могут быть соединенный вместе, чтобы получить общую подстроку целых строк. Из леммы Майкл Фекете^[9] что предел

${\displaystyle \gamma _{k}=\lim _{n\to \infty }{\frac {E[\lambda _{n,k}]}{n}}}$

существует, и равно супремум ценностей ${\displaystyle E[\lambda _{n,k}]/n}$. Эти предельные значения ${\displaystyle \gamma _{k}}$ - константы Хватала – Санкова.^[2]

Границы

Точные значения констант Хватала – Санкоффа остаются неизвестными, но были доказаны строгие оценки сверху и снизу.

Потому что ${\displaystyle \gamma _{k}}$ является супремумом значений ${\displaystyle E[\lambda _{n,k}]}$ каждая из которых зависит только от конечного распределения вероятностей, что является одним из способов доказательства строгих нижних оценок ${\displaystyle \gamma _{k}}$ было бы вычислить точные значения ${\displaystyle E[\lambda _{n,k}]}$; однако этот метод экспоненциально масштабируется в п, поэтому его можно реализовать только для малых значений п, что приводит к слабой нижней границе. В его докторской степени. докторской диссертации Владо Данчик первым предложил альтернативный подход, в котором детерминированный конечный автомат используется для чтения символов двух входных строк и создания (длинной, но не оптимальной) общей подпоследовательности этих входных данных. Поведение этого автомата на случайных входах можно проанализировать как Цепь Маркова, установившееся состояние которой определяет скорость, с которой он находит элементы общей подпоследовательности для больших значений п. Эта скорость обязательно является нижней границей постоянной Хватала – Санкоффа.^[10] Используя метод Данчика, с автоматом, пространство состояний которого буферизует самые последние час символов из двух входных строк, а также с дополнительными методами, позволяющими избежать дорогостоящего анализа устойчивой цепи Маркова в рамках этого подхода, Люкер (2009) смог выполнить компьютерный анализ с п = 15, что доказало ${\displaystyle \gamma _{2}\geq 0.788071}$.

Подобные методы могут быть распространены на небинарные алфавиты. Полученные таким образом нижние оценки для различных значений k находятся:^[4]

k	Нижняя граница ${\displaystyle \gamma _{k}}$
2	0.788071
3	0.671697
4	0.599248
5	0.539129
6	0.479452
7	0.44502
8	0.42237
9	0.40321
10	0.38656

Данчик и Патерсон (1995) также использовали теоретико-автоматные методы для доказательства верхних оценок констант Хватала – Санкова, и снова Люкер (2009) расширил эти результаты компьютерными расчетами. Полученная им верхняя оценка была ${\displaystyle \gamma _{2}\leq 0.826280}$. Этот результат опроверг гипотезу о Дж. Майкл Стил который ${\displaystyle \gamma _{2}=2/(1+{\sqrt {2}})}$, потому что это значение больше верхней границы.^[11] Неточные числовые данные предполагают, что ${\displaystyle \gamma _{2}}$ примерно ${\displaystyle 0.811}$, ближе к верхней границе, чем к нижней.^[12]

В пределе как k уходит в бесконечность, постоянные ${\displaystyle \gamma _{k}}$ растут обратно пропорционально квадратному корню из k. Точнее,^[3]

${\displaystyle \lim _{k\to \infty }\gamma _{k}{\sqrt {k}}=2.}$

Распределение длин LCS

Также было проведено исследование распределения значений самой длинной общей подпоследовательности, обобщающее исследование математического ожидания этого значения. Например, стандартное отклонение длины самой длинной общей подпоследовательности случайных строк длины п как известно пропорционально квадратному корню изп.^[13]

Одна из сложностей при выполнении такого рода анализа состоит в том, что случайные величины, описывающие, совпадают ли символы в разных парах позиций друг с другом, не являются независимыми друг от друга. Для более математически понятного упрощения самой длинной общей проблемы подпоследовательности, в которой допустимые совпадения между парами символов контролируются не тем, равны ли эти символы друг другу, а вместо этого независимыми случайными величинами с вероятностью 1 /k быть 1 и (k − 1)/k равного 0, было показано, что распределение длины самой длинной общей подпоследовательности контролируется Распределение Трейси – Уидома.^[14]

Рекомендации

1. Чватал, Вацлав; Санкофф, Дэвид (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Журнал прикладной теории вероятностей, 12: 306–315, Дои:10.2307/3212444, МИСТЕР  0405531.
2. Финч, Стивен Р. (2003), «5.20.2 Общие подпоследовательности», Математические константы, Энциклопедия математики и ее приложений, Cambridge University Press, стр. 384–385, ISBN  9780521818056.
3. Киви, Маркос; Лёбль, Мартин; Матушек, Иржи (2005), «Ожидаемая длина самой длинной общей подпоследовательности для больших алфавитов», Успехи в математике, 197 (2): 480–498, arXiv:математика / 0308234, Дои:10.1016 / j.aim.2004.10.012, МИСТЕР  2173842.
4. Киви, М .; Сото, Дж. (2009), «О предполагаемой связи между константами Хватала – Санкоффа нескольких последовательностей», Комбинаторика, теория вероятностей и вычисления, 18 (4): 517–532, arXiv:0810.1066, Дои:10.1017 / S0963548309009900, МИСТЕР  2507735.
5. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), "15.4", Введение в алгоритмы (2-е изд.), MIT Press and McGraw-Hill, pp. 350–355, ISBN  0-262-53196-8.
6. Масек, Уильям Дж .; Патерсон, Майкл С. (1980), «Более быстрый алгоритм вычисления расстояний редактирования строк», Журнал компьютерных и системных наук, 20 (1): 18–31, Дои:10.1016/0022-0000(80)90002-1, МИСТЕР  0566639.
7. Санкофф, Дэвид; Крускал, Джозеф Б. (1983), Искажения времени, редактирование строк и макромолекулы: теория и практика сравнения последовательностей, Эддисон-Уэсли.
8. Хант, Джеймс У .; Шимански, Томас Г. (1977), "Быстрый алгоритм для вычисления самых длинных общих подпоследовательностей", Коммуникации ACM, 20 (5): 350–353, Дои:10.1145/359581.359603, МИСТЕР  0436655.
9. Фекете, М. (1923), "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten", Mathematische Zeitschrift (на немецком), 17 (1): 228–249, Дои:10.1007 / BF01504345.
10. Данчик, Владо; Патерсон, Майк (1995), "Верхние границы ожидаемой длины самой длинной общей подпоследовательности двух двоичных последовательностей", Случайные структуры и алгоритмы, 6 (4): 449–458, Дои:10.1002 / RSA.3240060408, МИСТЕР  1368846.
11. Люкер, Джордж С. (2009), "Улучшенные оценки средней длины самых длинных общих подпоследовательностей", Журнал ACM, 56 (3), A17, Дои:10.1145/1516512.1516519, МИСТЕР  2536132.
12. Диксон, Джон Д. (2013), Самые длинные общие подпоследовательности в двоичных последовательностях, arXiv:1307.2796, Bibcode:2013arXiv1307.2796D.
13. Лембер, Юри; Мацингер, Генрих (2009), «Стандартное отклонение самой длинной общей подпоследовательности», Анналы вероятности, 37 (3): 1192–1235, arXiv:0907.5137, Дои:10.1214 / 08-AOP436, МИСТЕР  2537552.
14. Majumdar, Satya N .; Нечаев, Сергей (2005), "Точные асимптотические результаты для модели соответствия Бернулли выравнивания последовательностей", Физический обзор E, 72 (2): 020901, 4, arXiv:q-bio / 0410012, Bibcode:2005PhRvE..72b0901M, Дои:10.1103 / PhysRevE.72.020901, МИСТЕР  2177365, PMID  16196539.