Stałe Chvatala-Sankoffa - Chvátal–Sankoff constants

W matematyce , na stałe Chvátal-Sankoff są stałe matematyczne opisujące długości najdłuższych wspólnych podciągów z losowych ciągów . Chociaż udowodniono istnienie tych stałych, ich dokładne wartości nie są znane. Ich nazwa pochodzi od Václava Chvátala i Davida Sankoffa , którzy rozpoczęli ich badanie w połowie lat siedemdziesiątych.

Dla każdej dodatniej liczby całkowitej k istnieje jedna stała Chvátala-Sankoffa , gdzie k jest liczbą znaków w alfabecie, z których losowane są ciągi. Ciąg tych liczb rośnie odwrotnie proporcjonalnie do pierwiastka kwadratowego z k . Jednak niektórzy autorzy piszą „stałą Chvatala-Sankoffa”, aby odnieść się do , stałej zdefiniowanej w ten sposób dla alfabetu binarnego. ${\ Displaystyle \ gamma _ {k}}$${\displaystyle \gamma_{2}}$

tło

Wspólnym podciągiem dwóch ciągów S i T jest ciąg, którego znaki pojawiają się w tej samej kolejności (niekoniecznie kolejno) zarówno w S, jak iw T . Problem obliczania najdłuższego wspólnego podciągu został dobrze zbadany w informatyce. Można go rozwiązać w czasie wielomianowym przez programowanie dynamiczne ; ten podstawowy algorytm ma dodatkowe przyśpieszenia dla małych alfabetów ( Metoda Czterech Rusinów ), dla ciągów znaków z kilkoma różnicami, dla ciągów znaków z niewielką liczbą pasujących par znaków itp. Ten problem i jego uogólnienia na bardziej złożone formy odległości edycji mają ważne zastosowania w obszary, które obejmują bioinformatykę (w porównywaniu sekwencji DNA i białek oraz rekonstrukcji drzew ewolucyjnych ), geologii (w stratygrafii ) i informatyce (w porównywaniu danych i kontroli rewizji ).

Jedną z motywacji do badania najdłuższych wspólnych podciągów losowych ciągów, podaną już przez Chvátala i Sankoffa, jest kalibracja obliczeń najdłuższych wspólnych podciągów na ciągach, które nie są losowe. Jeśli takie obliczenie zwróci podciąg, który jest znacznie dłuższy niż ten, który zostałby uzyskany losowo, można wywnioskować z tego wyniku, że dopasowanie jest znaczące lub znaczące.

Definicja i istnienie

Stałe Chvatala-Sankoffa opisują zachowanie następującego procesu losowego. Mając parametry n i k , wybierz dwa ciągi o długości n S i T z tego samego alfabetu k- symbolu, przy czym każdy znak każdego ciągu jest wybierany losowo jednakowo , niezależnie od wszystkich innych znaków. Oblicz najdłuższy wspólny podciąg tych dwóch ciągów i niech będzie zmienną losową, której wartością jest długość tego podciągu. Następnie wartość oczekiwana w to (do niższego rzędu warunki) proporcjonalnie do  n , i k th Chvátal-Sankoff stałej jest współczynnikiem proporcjonalności . ${\ Displaystyle \ lambda _ {n, k}}$${\ Displaystyle \ lambda _ {n, k}}$${\ Displaystyle \ gamma _ {k}}$

Dokładniej, oczekiwana wartość jest superaddytywna : dla wszystkich m i n , . Jest tak, ponieważ jeśli łańcuchy o długości m  +  n są podzielone na podrzędnymi długości m i n , a najdłuższe wspólne subsekwencje tych podciągów występują, mogą być łączone ze sobą w celu uzyskania wspólnego podciągu całych łańcuchów. Z lematu Michaela Fekete wynika, że granica${\ Displaystyle E [\ lambda _ {n, k}]}$${\ Displaystyle E [\ lambda _ {m + n, k}] \ geq e [\ lambda _ {m, k}] + E [\ lambda _ {n, k}]}$

${\ Displaystyle \ gamma _ {k} = \ lim _ {n \ do \ infty} {\ Frac {E [\ lambda _ {n, k}]} {n}}}$

istnieje i jest równa najwyższej wartości . Te wartości graniczne to stałe Chvatala-Sankoffa. ${\ Displaystyle E [\ lambda _ {n, k}] / n}$${\ Displaystyle \ gamma _ {k}}$

Miedza

Dokładne wartości stałych Chvatala-Sankoffa pozostają nieznane, ale rygorystyczne górne i dolne granice zostały udowodnione.

Ponieważ jest to najwyższe wartości, z których każda zależy tylko od skończonego rozkładu prawdopodobieństwa, jednym ze sposobów udowodnienia rygorystycznych dolnych granic byłoby obliczenie dokładnych wartości ; jednak ta metoda skaluje się wykładniczo w n , więc może być zaimplementowana tylko dla małych wartości n , co prowadzi do słabej dolnej granicy. W swoim doktoracie Vlado Dančík jest pionierem alternatywnego podejścia, w którym deterministyczny automat skończony jest używany do odczytywania symboli dwóch ciągów wejściowych i wytwarzania (długiego, ale nie optymalnego) wspólnego podciągu tych danych wejściowych. Zachowanie tego automatu na losowych wejściach można analizować jako łańcuch Markowa , którego stan ustalony określa szybkość z jaką znajduje elementy wspólnego podciągu dla dużych wartości n . Ta stawka jest koniecznie dolną granicą stałej Chvatala-Sankoffa. Korzystając z metody Dančíka, z automatem, którego przestrzeń stanów buforuje najnowsze znaki h z jego dwóch ciągów wejściowych, oraz z dodatkowymi technikami pozwalającymi uniknąć kosztownej analizy łańcuchów Markowa w stanie ustalonym tego podejścia, Lueker (2009) był w stanie przeprowadzić analiza komputerowa z n  = 15, która wykazała . ${\ Displaystyle \ gamma _ {k}}$${\ Displaystyle E [\ lambda _ {n, k}]}$${\ Displaystyle \ gamma _ {k}}$${\ Displaystyle E [\ lambda _ {n, k}]}$${\ Displaystyle \ gamma _ {2} \ geq 0.788071}$

Podobne metody można uogólnić na alfabety niebinarne. Otrzymane w ten sposób dolne granice dla różnych wartości k to:

k	Dolna granica włączona ${\ 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

Dančík i Paterson (1995) również zastosowali metody teorii automatów, aby udowodnić górne granice stałych Chvátala-Sankoffa, a Lueker (2009) rozszerzył te wyniki o obliczenia komputerowe. Górna granica, którą uzyskał to . Ten wynik obalił przypuszczenie J. Michaela Steele'a, że , ponieważ ta wartość jest większa niż górna granica. Nieścisłe dane liczbowe sugerują, że jest to w przybliżeniu , bliżej górnej granicy niż dolnej granicy. ${\ Displaystyle \ gamma _ {2} \ równoważnik 0,826280}$${\ Displaystyle \ gamma _ {2} = 2 / (1 + {\ sqrt {2}})}$${\displaystyle \gamma_{2}}$${\ Displaystyle 0,811}$

W granicy, gdy k zmierza do nieskończoności, stałe rosną odwrotnie proporcjonalnie do pierwiastka kwadratowego z k . Dokładniej, ${\ Displaystyle \ gamma _ {k}}$

${\ Displaystyle \ lim _ {k \ do \ infty} \ gamma _ {k} {\ sqrt {k}} = 2.}$

Rozkład długości LCS

Prowadzono również badania nad rozkładem wartości najdłuższego wspólnego podciągu, uogólniając badanie oczekiwań tej wartości. Na przykład wiadomo , że odchylenie standardowe długości najdłuższego wspólnego podciągu losowych ciągów o długości n jest proporcjonalne do pierwiastka kwadratowego z  n .

Jedną z komplikacji w przeprowadzaniu tego rodzaju analizy jest to, że zmienne losowe opisujące, czy znaki w różnych parach pozycji pasują do siebie, nie są od siebie niezależne. Dla bardziej przystępnego matematycznie uproszczenia problemu najdłuższego wspólnego podciągu, w którym dozwolone dopasowania między parami symboli nie są kontrolowane przez to, czy te symbole są sobie równe, ale przez niezależne zmienne losowe z prawdopodobieństwem 1/ k równym 1 i ( k  − 1)/ k równego 0, wykazano, że rozkład najdłuższego wspólnego podciągu jest kontrolowany przez rozkład Tracy-Widoma .

Bibliografia