Nejbližší řetězec - Closest string
v teoretická informatika, nejbližší řetězec je NP-tvrdé výpočetní problém,[1] který se snaží najít geometrický střed sady vstupních řetězců.
Pro pochopení slova „střed“ je nutné definovat vzdálenost mezi dvěma řetězci. Obvykle je tento problém studován pomocí Hammingova vzdálenost na mysli.
Formální definice
Více formálně, vzhledem n délka-m struny s1, s2, ..., sn, nejbližší problém s řetězci hledá novou délku -m tětiva s takhle d(s,si) ≤ k pro všechny i, kde d označuje Hammingova vzdálenost, a kde k je co nejmenší.[2] A rozhodovací problém verze nejbližšího problému s řetězcem, který je NP-kompletní, místo toho bere k jako další vstup a otázky, zda je v Hammingově vzdálenosti řetězec k všech vstupních řetězců.[1]
Na nejbližší problém s řetězci lze pohlížet jako na zvláštní případ generika 1-středový problém ve kterém jsou vzdálenosti mezi prvky měřeny pomocí Hammingovy vzdálenosti.
Motivace
v bioinformatika, nejbližším řetězcovým problémem je intenzivně studovaný aspekt problému hledání signálů v DNA.
Zjednodušení a redukce dat
Instance nejbližšího řetězce mohou obsahovat informace, které nejsou pro problém zásadní. V určitém smyslu obsahuje obvyklý vstup nejbližšího řetězce informace, které nepřispívají k tvrdosti problému. Například pokud některé řetězce obsahují znak A, ale žádný znak neobsahuje z, nahradí všechny As s zs by přineslo v podstatě ekvivalentní instanci, to znamená: z řešení upravené instance lze obnovit původní řešení a naopak.
Normalizace vstupu
Když jsou všechny vstupní řetězce, které sdílejí stejnou délku, zapsány na sebe, tvoří matici. Některé typy řádků mají v zásadě stejné důsledky pro řešení. Například nahrazení sloupce položkami (A, A, b) s jiným sloupcem (X, X, y) může vést k odlišnému řetězci řešení, ale nemůže ovlivnit řešitelnost, protože oba sloupce vyjadřují stejnou strukturu, viz. první dva záznamy jsou stejné, ale liší se od třetího.
Instance vstupu může být normalizováno tak, že v každém sloupci nahradíte znak, který se nejčastěji vyskytuje u A, znak, který se vyskytuje jako druhý nejčastěji u b, a tak dále. Vzhledem k řešení normalizované instance lze původní instanci najít přemapováním znaků řešení na původní verzi v každém sloupci.
Pořadí sloupců nepřispívá k tvrdosti problému. To znamená, že pokud permutujeme všechny vstupní řetězce podle určité permutace π a získáme řetězec řešení s k této upravené instanci, pak π−1(s) bude řešením původní instance.
Příklad
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Closest-string_problem_example_svg.svg/220px-Closest-string_problem_example_svg.svg.png)
Daná instance se třemi vstupními řetězci uvwx, xuwv, a xvwu. To by mohlo být napsáno jako matice takto:
u | proti | w | X |
X | u | w | proti |
X | proti | w | u |
První sloupec má hodnoty (u, X, X). Tak jako X je postava, která se objevuje nejčastěji, nahradíme ji Aa vyměníme u, druhý nejčastěji znak, od b, získání nového prvního sloupce (b, A, A). Druhý sloupec má hodnoty (proti, u, proti). Pokud jde o první sloupec, proti je nahrazen A a u je nahrazen b, získání nového druhého sloupce (A, b, A). Stejné provedení se všemi sloupci dává normalizovanou instanci
b | A | A | A |
A | b | A | b |
A | A | A | C |
Redukce dat získaná z normalizace
Normalizace vstupu zmenší velikost abecedy na maximálně počet vstupních řetězců. To může být užitečné pro algoritmy, jejichž doba běhu závisí na velikosti abecedy.
Přibližnost
Li a kol. vyvinul a schéma aproximace v polynomiálním čase[3] což je prakticky nepoužitelné kvůli velkým skrytým konstantám.
Opravitelnost s pevnými parametry
Nejbližší řetězec lze vyřešit v , kde k je počet vstupních řetězců, L je délka všech řetězců a d je požadovaná maximální vzdálenost od řetězce řešení k libovolnému vstupnímu řetězci.[4]
Vztahy k dalším problémům
Nejbližší řetězec je speciální případ obecnějšího nejbližší podřetězec problém, který je přísně obtížnější. Zatímco nejbližší řetězec se ukáže být fixovatelný parametr v mnoha ohledech je nejbližší podřetězec W [1] - tvrdý s ohledem na tyto parametry.
Reference
- ^ A b Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), „Rozlišování problémů s výběrem řetězců“, Informace a výpočet, 185 (1): 41–55, doi:10.1016 / S0890-5401 (03) 00057-9, PAN 1994748
- ^ Bin Ma a Xiaming Sun (2008), „Efektivnější algoritmy pro nejbližší problémy s řetězci a podřetězci“ (PDF), Výzkum v oblasti výpočetní molekulární biologie, LNCS, 4955, Springer, str. 396–409, doi:10.1007/978-3-540-78839-3_33, ISBN 978-3-540-78838-6CS1 maint: používá parametr autoři (odkaz)
- ^ M. Li, B. Ma a L. Wang. (2002), „Na nejbližší řetězec a problémy s řetězci.“ (PDF), Deník ACM, 49 (2): 157–171, arXiv:cs / 0002012, doi:10.1145/506147.506150CS1 maint: používá parametr autoři (odkaz)
- ^ Jens Gramm, Rolf Niedermeier a Peter Rossmanith (2003), „Algoritmy s pevnými parametry pro nejbližší řetězec a související problémy“, Algorithmica, 37: 25–42, CiteSeerX 10.1.1.61.736, doi:10.1007 / s00453-003-1028-3CS1 maint: používá parametr autoři (odkaz)