Algoritmy pro práci s DNA a problém P vs. NP

Pavel Houser , 19. únor 2017 10:00 0 komentářů
Algoritmy pro práci s DNA a problém P vs. NP

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.


Komentáře

RSS 

Komentujeme

Virtuální realitou proti strachu ze smrti

Pavel Houser , 18. červenec 2017 07:00
Pavel Houser

Lidé, kteří reportují „zážitky blízké smrti“, pak mnohdy mají ze smrti menší strach. Nedalo by se to...

Více






Kalendář

22. 07.

27. 07.
Black Hat 2017
27. 07.

30. 07.
Defcon 2017
27. 08.

31. 08.
VMworld 2017
RSS 

Zprávičky

V Praze se instalují první chytré lavičky připojené přes síť LoRa

Pavel Houser , 20. červenec 2017 13:28

Lavička TreeSmart nabízí wi-fi připojení, nabíjení mobilních zařízení a senzory snímající vlhkost, t...

Více 1 komentářů

SUSE a Supermicro uzavírají globální partnerství

Pavel Houser , 20. červenec 2017 10:00

Firmy poskytnou řešení pro kritickou infrastrukturu, softwarově definovaná datová centra a integrova...

Více 0 komentářů

Chytrou domácnost vzdáleně řídí 17 % Čechů

Pavel Houser , 20. červenec 2017 09:00

Řízení chytrých domácností v ČR láká hlavně kvůli kontrole nákladů za energie. Ve světě je hlavní mo...

Více 0 komentářů

Starší zprávičky

PayPal a Visa budou nabízet debetní karty v Evropě

ČTK , 20. červenec 2017 08:00

PayPal svou bankovní licenci dosud využíval především k pokladním službám....

Více 0 komentářů

Dell uvádí servery PowerEdge 14. generace

Pavel Houser , 19. červenec 2017 14:19

Nové servery PowerEdge 14. generace přinášejí podle dodavatele architekturu, optimalizovanou pro sof...

Více 0 komentářů

Zoot vydá čtyřleté veřejně obchodovatelné dluhopisy s úrokem 6,5 %

ČTK , 19. červenec 2017 13:59

Největší tuzemský internetový obchod s módou Zoot vydá podřízené dluhopisy v celkovém objemu 150 mil...

Více 0 komentářů

Atari představuje novou herní konzoli Ataribox

ČTK , 19. červenec 2017 11:51

Francouzský výrobce videoher Atari ukázal herní konzoli Ataribox, která je první novou konzolí firmy...

Více 1 komentářů