Kortaste vanliga supersekvensproblem

Inom datavetenskap är den kortaste vanliga supersekvensen av två sekvenser X och Y den kortaste sekvensen som har X och Y som undersekvenser . Detta är ett problem nära relaterat till det längsta vanliga följdproblemet . Givet två sekvenser X = < x ₁ ,...,x _m > och Y = < y ₁ ,...,y _n > är en sekvens U = < u ₁ ,..., _uk > en vanlig supersekvens av X och Y om föremål kan tas bort från U för att producera X och Y .

A shortest common supersequence (SCS) är en vanlig supersekvens med minimal längd. I det kortaste vanliga supersekvensproblemet ges två sekvenser X och Y , och uppgiften är att hitta en kortast möjliga gemensam supersekvens av dessa sekvenser. I allmänhet är en SCS inte unik.

För två ingångssekvenser kan en SCS enkelt bildas från en längsta gemensam delsekvens (LCS). Till exempel, den längsta vanliga följden av X $[1..m]=abcbdab$ och Y $[1..n]=bdcaba$ är Z $[1..L]=bcba$ . Genom att infoga icke-LCS-symbolerna i Z samtidigt som deras ursprungliga ordning bevaras, får vi en kortast gemensam supersekvens U $[1..S]=abdcabdab$ . Speciellt gäller ekvationen $L+S=m+n$ för vilka två inmatningssekvenser som helst.

Det finns inget liknande förhållande mellan kortaste gemensamma supersekvenser och längsta gemensamma subsekvenser av tre eller flera ingångssekvenser. (Särskilt LCS och SCS är inte dubbla problem .) Båda problemen kan dock lösas i $O(n^{k})$ tid med hjälp av dynamisk programmering, där $k$ är antalet sekvenser, och $n$ är deras maximala längd. För det allmänna fallet med ett godtyckligt antal ingångssekvenser är problemet NP-hårt .

Kortaste vanliga supersträngen

Det närbesläktade problemet med att hitta en sträng med minsta längd som är en supersträng av en ändlig uppsättning strängar S = { s ₁ , s ₂ ,..., s _n } är också NP-hårt. Flera konstanta faktorapproximationer har föreslagits genom åren, och den nuvarande mest kända algoritmen har en approximationsfaktor på 2,475. Emellertid är kanske den enklaste lösningen att omformulera problemet som en instans av viktat set-täckning på ett sådant sätt att vikten av den optimala lösningen till set-cover-instansen är mindre än två gånger längden av den kortaste supersträngen S . Man kan sedan använda O(log( n ))-approximationen för viktad set-cover för att få en O(log( n ))-approximation för den kortaste supersträngen (observera att detta inte är en konstant faktorapproximation).

För alla strängar x i det här alfabetet, definiera P ( x ) som uppsättningen av alla strängar som är delsträngar till x . Förekomsten I av uppsättningsomslag är formulerad enligt följande:

• Låt M vara tom.
• _För varje par av strängar si och sj , om de sista k symbolerna för si _är desamma som de första _k symbolerna för sj , lägg sedan till en _sträng till M som består av sammanlänkningen med maximal överlappning av si _med s _j .
• Definiera universum ${\mathcal {U}}$ för den uppsatta omslagsinstansen till S
• Definiera uppsättningen av delmängder av universum att vara { P ( x ) | x ∈ S ∪ M }
• Definiera kostnaden för varje delmängd P (x) till | x |, längden av x .

Förekomsten I kan sedan lösas med hjälp av en algoritm för viktat uppsättningstäckning, och algoritmen kan mata ut en godtycklig sammanfogning av strängarna x för vilka den viktade uppsättningstäckningsalgoritmen matar ut P ( x ).

Exempel

Betrakta mängden S = { abc, cde, fab }, som blir universum för den viktade uppsättningsomslagsinstansen. I det här fallet är M = { abcde, fabc }. Då är uppsättningen av delmängder av universum

${\begin{aligned} \{P(x)|x\in S\cup M\}&=\{P(x)|x\in \{abc,cde,fab,abcde,fabc\}\}\\&=\{P (abc),P(cde),P(fab),P(abcde),P(fabc)\}\}\\&=\{\{a,b,c,ab,bc,abc\},\ {c,d,e,cd,de,cde\},\ldots ,\{f,a,b,c,fa,ab,bc,fab,abc,fabc\}\}\}\\\end{ Justerat}}$

som kostar 3, 3, 3, 5 respektive 4.

•    Garey, Michael R .; Johnson, David S. (1979). Datorer och svårhanterlighet: En guide till teorin om NP-fullständighet . WH Freeman. sid. 228 A4.2: SR8 . ISBN 0-7167-1045-5 . Zbl 0411.68039 .
•    Szpankowski, Wojciech (2001). Genomsnittlig fallanalys av algoritmer på sekvenser . Wiley-Interscience-serien i diskret matematik och optimering. Med ett förord ​​av Philippe Flajolet. Chichester: Wiley. ISBN 0-471-24063-X . Zbl 0968.68205 .
•   Vazirani, Vijay V. (2001), Approximation Algorithms , Springer-Verlag, ISBN 3-540-65367-8

externa länkar

• Dictionary of Algoritms and Data Structures: kortaste vanliga supersekvensen