V Teoretické informatice , a zejména v algoritmickém textu , je nejbližší řetězec (anglický nejbližší řetězec ) sady dat řetězců znaků řetězcem kanálu minimální vzdálenosti, podle Hammingovy vzdálenosti . Hledání nejbližšího řetězce je algoritmický problém NP-hard .
Pro pět řetězů
| BARACADABRA |
| ABRAACDABRA |
| RBRACADABCA |
| ACRACADABCA |
| ABRADADABCA |
nejbližší kanál je
| ABRACADABRA |
Je vzdálený 2 od daných kanálů. Náhody jsou označeny červeně:
| BA RACADABRA |
| ABRA AC DABRA |
| R BRACADAB C C |
| A C RACADAB C A |
| ABRA D ADAB C A |
Vzhledem k tomu, že n řetězců s 1 , ..., s n má stejnou délku m , nejbližší problém řetězce spočívá v určení nového řetězce s délky m tak, že d ( s , s i ) ≤ k pro všechna i , kde d je vzdálenost Hammingova , a kde k je tak malý, jak je to možné. Odpovídající rozhodnutí problém , který je NP-úplný , rovněž za celé číslo k, jako vstup a zeptá, zda je řetězec, který je Hammingova vzdálenost je maximálně k všech uvedených řetězců. Problém je NP-těžký i na binární abecedě.
V bioinformatice je problémem s nejbližším řetězcem hodně studovaný aspekt problému detekce signálů v DNA . Problém má také aplikace v teorii kódu (problém s minimálním poloměrem). Nejbližší dílčí problém formalizuje biologické aplikace při hledání konzervovaných oblastí, identifikaci cílů genetických léků a generování genetických sond v molekulární biologii. V textových algoritmech jde o problém kombinatoriky znakových řetězců. Tento problém řetězce a další, které vznikají v různých aplikacích od těžby textu po biologickou sekvenční analýzu, jsou často NP obtížné . To motivuje k hledání zvláštních vyřešitelných případů s pevnými parametry těchto problémů. To dává smysl v případech, kdy existuje několik přirozeně asociovaných parametrů, jako je velikost abecedy, počet řetězců nebo horní hranice vzdálenosti.
Na nejbližší řetězový problém lze pohlížet geometricky jako na příklad 1-středového problému s Hammingovou vzdáleností jako jeho vzdáleností.
Instance problému s nejbližším řetězcem mohou obsahovat informace, které pro problém nemají smysl, nebo které nepřispívají k obtížnosti problému. Například, pokud některé řetězce obsahují znak A , a žádný obsahovat znak Z , který nahrazuje veškeré A se z poskytuje v podstatě ekvivalentní instance, která je, z roztoku modifikovaného například originální řešení lze snadno obnovit a naopak.
Psaním vstupních řetězců jeden pod druhým získáme matici. Některé typy linek mají na řešení v podstatě stejný vliv. Například nahrazení sloupce, který má položky ( a , a , b ) sloupcem ( x , x , y ), může vést k jinému řetězci řešení, ale nemusí to ovlivnit solventnost, protože oba sloupce vyjadřují stejnou strukturu. , kde jsou první dva záznamy stejné, ale odlišné od třetího.
Instanci vstupu lze normalizovat tak, že v každém sloupci nahradíte znak, který se nejčastěji vyskytuje znakem a , znak, který se objeví na druhém místě b , atd. Vzhledem k řešení normalizované instance lze původní instanci obnovit nahrazením znaků v řešení jejich původní verzí v každém sloupci. Pořadí sloupců nepřispívá k obtížnosti problému. To znamená, že pokud permutujeme vstupní řetězce podle nějaké permutace π a pokud dostaneme řetězec řešení s k této upravené instanci, pak π −1 ( s ) je řešením původní instance.
Uvažujeme instanci vytvořenou ze tří slov uvwx , xuwv a xvwu (viz diagram výše). Ve formě matice získáme následující tabulku:
| u | proti | w | X |
| X | u | w | proti |
| X | proti | w | u |
V prvním sloupci ( u , x , x ) se nejčastěji (dvakrát) objevuje symbol x ; nahradíme jej za a znak u za b , což dává nový první sloupec ( b , a , a ). Druhý sloupec ( v , u , v ) je nahrazen stejnou strategií ( a , b , a ). Tím, že budeme postupovat stejným způsobem pro ostatní sloupce, skončíme na
| b | na | na | na |
| na | b | na | b |
| na | na | na | vs. |
Normalizace má za následek, že velikost abecedy se maximálně rovná počtu vstupních řetězců. To může být užitečné pro algoritmy, jejichž výpočetní doba závisí na velikosti abecedy.
Li a kol. popsali aproximační schéma v polynomiálním čase , ale které je v praxi nepoužitelné kvůli velkým skrytým konstantám.
Nejbližší problém řetězce lze vyřešit pomocí O ( nL + nd × d d ) , kde n je počet řetězců uvedených jako vstup, L je společná délka všech řetězců a d je požadovaná vzdálenost od řešení ke všem daným struny. Je tedy ve třídě parametrizované složitosti FPT ( fixed-parameterractable ).
Problém nejbližšího řetězce je speciální případ obecnějšího problému nejbližšího podřetězce (in) je přísně těžší. Zatímco problém s nejbližším řetězcem je fixní parametr, který je možné dopravit různými způsoby, problém s podřetězcem W [1] je vzhledem k těmto parametrům obtížný . Kernelization těchto a související problémy je předmětem podrobné studie, která ukazuje, že buď můžeme získat polynomiální jádro, nebo že jádro, není možné získat za obvyklých předpokladů teorie složitosti, a zejména na exponenciální čas hypotéza (ETH ). Tyto problémy spočívají v nalezení substruktury nebo nadstavby společné pro danou sadu řetězců. Nejzákladnější problémy jsou nejdelší společná podposloupnost je nejkratší společný super-sekvence, a nejmenší společný sekvence. Kromě toho existuje obecnější problém zarovnání více sekvencí , který je nanejvýš důležitý v biologické sekvenční analýze .