Chvátal–Sankoff-konstanter

Inom matematiken är Chvátal –Sankoff-konstanterna matematiska konstanter som beskriver längden på de längsta vanliga undersekvenserna av slumpmässiga strängar . Även om förekomsten av dessa konstanter har bevisats, är deras exakta värden okända. De är uppkallade efter Václav Chvátal och David Sankoff , som började undersöka dem i mitten av 1970-talet.

Det finns en Chvátal–Sankoff-konstant $\gamma _{k}$ för varje positivt heltal k , där k är antalet tecken i alfabetet som de slumpmässiga strängarna dras från. Följden av dessa tal växer omvänt proportionellt mot kvadratroten av k . Men vissa författare skriver "Chvátal–Sankoff-konstanten" för att hänvisa till ${\displaystyle \gamma _{2}} ,$ konstanten som definieras på detta sätt för det binära alfabetet.

Bakgrund

En vanlig undersekvens av två strängar S och T är en sträng vars tecken visas i samma ordning (inte nödvändigtvis i följd) både i S och i T . Problemet med att beräkna en längsta gemensamma undersekvens har studerats väl inom datavetenskap. Det kan lösas i polynomtid genom dynamisk programmering ; den här grundläggande algoritmen har ytterligare hastighetshöjningar för små alfabet ( metoden för fyra ryska ), för strängar med få skillnader, för strängar med få matchande teckenpar, etc. Detta problem och dess generaliseringar till mer komplexa former av redigeringsavstånd har viktiga tillämpningar i områden som inkluderar bioinformatik (i jämförelse av DNA- och proteinsekvenser och rekonstruktion av evolutionära träd ), geologi (i stratigrafi ) och datavetenskap (i datajämförelse och revisionskontroll ).

Ett motiv för att studera de längsta vanliga delsekvenserna av slumpmässiga strängar, som redan ges av Chvátal och Sankoff, är att kalibrera beräkningarna av längsta vanliga delsekvenser på strängar som inte är slumpmässiga. Om en sådan beräkning returnerar en efterföljd som är betydligt längre än vad som skulle erhållas slumpmässigt, kan man utifrån detta resultat dra slutsatsen att matchningen är meningsfull eller signifikant.

Definition och existens

Chvátal–Sankoff-konstanterna beskriver beteendet för följande slumpmässiga process. Givet parametrarna n och k , välj två längd -n strängar S och T från samma k -symbolalfabet, med varje tecken i varje sträng vald enhetligt slumpmässigt , oberoende av alla andra tecken. Beräkna en längsta gemensamma undersekvens av dessa två strängar och låt $\lambda _{n,k}$ vara den slumpmässiga variabeln vars värde är längden på denna undersekvens. Då är det förväntade värdet på $\lambda _{n,k}$ (upp till termer av lägre ordning) proportionellt mot n , och den k :te Chvátal–Sankoff-konstanten $\gamma _ {k}$ är proportionalitetskonstanten .

Mer exakt är det förväntade värdet $} [\lambda _{n,k}]}$ E superadditivt : för alla m och n , $\operatörsnamn {E} [\lambda _{m+n,k}]\geq \operatörsnamn {E} [\lambda _{m,k}]+\operatörsnamn {E} [\lambda _{n,k}]$ . Detta beror på att om strängar med längden m + n bryts upp i delsträngar med längderna m och n och de längsta gemensamma delsekvenserna av dessa delsträngar hittas, kan de sammanfogas för att få en gemensam delsträng av hela strängarna. Det följer av ett lemma av Michael Fekete att gränsen

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

existerar och är lika med det högsta av värdena $\operatorname {E} [\lambda _{n,k}]/n$ . Dessa gränsvärden $\gamma _{k}$ är Chvátal–Sankoff konstanterna.

Gräns

De exakta värdena för Chvátal-Sankoff-konstanterna är fortfarande okända, men rigorösa övre och nedre gränser har bevisats.

Eftersom $\gamma _{k}$ är en supremum av värdena $\operatorname {E} [\lambda _{n,k}]$ som var och en endast beror på på en ändlig sannolikhetsfördelning skulle ett sätt att bevisa rigorösa nedre gränser för $\operatorname {E} [\lambda _{n,k}]$$\displaystyle \gamma _{k}}$ vara att beräkna de exakta värdena för ; denna metod skalar dock exponentiellt i n , så den kan endast implementeras för små värden på n , vilket leder till en svag nedre gräns. I sin Ph.D. Vlado Dančík var pionjär med ett alternativt tillvägagångssätt där en deterministisk finit automat används för att läsa symboler för två ingångssträngar och producera en (lång men inte optimal) gemensam undersekvens av dessa indata. Beteendet hos denna automat på slumpmässiga ingångar kan analyseras som en Markov-kedja , vars stabila tillstånd bestämmer hastigheten med vilken den hittar delar av den gemensamma undersekvensen för stora värden på n . Denna hastighet är nödvändigtvis en nedre gräns för Chvátal–Sankoff-konstanten. Genom att använda Dančíks metod, med en automat vars tillståndsutrymme buffrar de senaste h- tecken från dess två inmatningssträngar, och med ytterligare tekniker för att undvika den dyra steady-state Markov-kedjeanalysen av detta tillvägagångssätt, kunde Lueker (2009) utföra en datoriserad analys med n = 15 som visade att $\gamma _{2}\geq 0,788071$ .

Liknande metoder kan generaliseras till icke-binära alfabet. Nedre gränser som erhålls på detta sätt för olika värden på k är:

k	Nedre gräns på $\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 & Paterson (1995) använde också automatteoretiska metoder för att bevisa övre gränser för Chvátal–Sankoff-konstanterna, och återigen utökade Lueker (2009) dessa resultat med datoriserade beräkningar. Den övre gränsen han fick var $\gamma _{2}\leq 0,826280$ . Detta resultat motbevisade en gissning av J. Michael Steele att ${\displaystyle \gamma _{2}=2/(1+{\sqrt {2}})} ,$ eftersom detta värde är större än den övre gränsen. Icke rigorösa numeriska bevis tyder på att $\gamma _{2}$ är ungefär ${\displaystyle 0,811} ,$ närmare den övre gränsen än den nedre gränsen.

I gränsen när k går till oändligheten växer konstanterna $\gamma _{k}$ omvänt proportionellt mot kvadratroten ur k . Mer exakt,

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

Fördelning av LCS-längder

Det har också gjorts forskning om fördelningen av värden av den längsta gemensamma undersekvensen, vilket generaliserar studiet av förväntan på detta värde. Till exempel standardavvikelsen för längden av den längsta gemensamma undersekvensen av slumpmässiga strängar med längden n känd för att vara proportionell mot kvadratroten ur n .

En komplikation med att utföra denna typ av analys är att de slumpvariabler som beskriver om tecknen i olika positionspar matchar varandra inte är oberoende av varandra. För en mer matematiskt löslig förenkling av det längsta vanliga följdproblemet, där de tillåtna matchningarna mellan symbolpar inte styrs av om dessa symboler är lika med varandra utan istället av oberoende slumpvariabler med sannolikhet 1/k att vara 1 och ( k − 1)/ k av att vara 0, har det visats att fördelningen av den längsta gemensamma undersekvenslängden styrs av Tracy–Widom-fördelningen .