Genetici a bioinformatici už asi 40 let používají k porovnávání sekvencí DNA tzv. Wagner-Fischerův algoritmus. Tímto způsobem lze zjistit minimální počet elementárních operací, jimiž jednu sekvenci dokážeme přeměnit na druhou, tedy rozdílnost obou řetězců.
Za elementární operace považujeme vložení nebo smazání „písmene“ nebo jeho přepis za jiné písmeno. (Poznámka: někdy se za elementární počítá i výměna sousedních bází, zde zřejmě půjde tedy o dvě operace – editaci nezávisle na dvou místech.) Stejný algoritmus lze použít i ke stanovení „evoluce“ textů, které se od sebe podobně jako DNA opakovaně a dlouhodobě opisovaly, nikoliv však bezchybně – příkladem jsou biblické texty.
Složitost (výpočetní náročnost, čas k řešení úlohy) Wagner-Fischerova algoritmu závisí na součinu délky obou řetězců DNA. (Algoritmus pracuje s obrovskou tabulkou, kdy jeden řetězec představuje řádek a druhý sloupec – odtud ona součinová náročnost.) Protože porovnáváme řetězce podobné, je tedy zhruba kvadratickou funkcí délky každého z nich. Kvadratická složitost algoritmu není žádná katastrofa, i tak se ale po celou dobu mnoho lidí snaží přijít s efektnějším postupem. Výzkumníci z MITu nyní tvrdí, že celé úsilí je zřejmě marné – algoritmus se za celou dobu nepodařilo zrychlit, prostě proto, že to nejde. Vzhledem k tomu, kolik času se na tento problém už vynaložilo, má ovšem i negativní výsledek svou cenu.
Profesor počítačové vědy a spoluautor nového výzkumu Piotr Indyk uvádí, že jeho důkaz efektivity Wagner-Fischerova algoritmu má vztah ještě k řadě dalších informatických problémů. Výzkumníci přesněji řečeno dokázali, že problém porovnávání řetězců DNA souvisí s problémem splnitelnosti, tedy známé NP úplné úloze. Problém splnitelnosti (satisfiability) se v rámci popsané logiky dělí na dvě zhruba stejně velké skupiny prvků, ty pak budou odpovídat řádků a sloupcům tabulky. Není to zrovna očividné (pochopitelně, jinak by taková spojitost už někoho napadla dávno), nicméně výsledek má znít: pokud by porovnávání sekvencí DNA bylo řešitelné rychleji než v kvadratickém čase, pak by problém splnitelnosti by byl řešitelný rychleji než exponenciálně. A jelikož problém splnitelnost spadá do kategorie NP úplných, současně by to tedy znamenalo důkaz o vztahu polynomiálních a nedeterministicky polynomiálních (NP) úloh – 1 z hlavních problémů současné matematiky, na jejichž řešení vypsal Clayův ústav cenu milion dolarů. A konečně závěr z toho všeho: Protože skoro nikdo nevěří, že NP by se rovnalo P, nemá asi cenu se pokoušet ani o vylepšení Wagner-Fischerova algoritmu.
Zdroj: MIT News
Poznámky:
Otázky kolem P vs. NP se sice pokládají za jednu z mála záhad současné matematiky, které jsou nějak přístupné i neprofesionálům, nicméně i zde už bylo publikováno množství „důkazů“, které nakonec neobstály.
Platí uvedená spojitost i naopak? Tj. pokud nějakým jiným způsobem dokážeme, že Wagner-Fischerův algoritmus je optimální, bude to představovat i důkaz, že P je různé od NP?
Problém lze řešit také analogově: čím podobnější DNA, tím ochotněji se spolu příslušná vlákna spojí do dvojšroubovice, respektive ta bude stabilnější. Lze tedy porovnávat teplotu, při které se obě vlákna od sebe oddělí; teplota rozpadu dvojšroubovice je mírou podobnosti. Samozřejmě ve chvíli, kdy máme k dispozici osekvenovaná data, je jejich softwarové zpracování už mnohem „čistší“, než cokoliv provádět ve zkumavce.
