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

Deset minut s Einsteinem

Richard Jan Voigts , 18. listopad 2017 10:45
Richard Jan Voigts

Při návštěvě Švýcarska jsme strávili den na Eidgenoessiche Technische Hochschule Zurich – Swiss Fede...

Více







RSS 

Zprávičky

Vláda USA se snaží zablokovat spojení AT&T a Time Warner

ČTK , 21. listopad 2017 10:55

Americké ministerstvo spravedlnosti podalo žalobu s cílem zablokovat spojení telekomunikační společn...

Více 0 komentářů

Ve 3. čtvrtletí se prodeji PC v ČR dařilo

ČTK , 21. listopad 2017 09:00

Za první tři čtvtletí jako celek ale trh meziročně klesl o 3 % na 679 800 kusů. Stagnují i tradičn...

Více 0 komentářů

"Čínský Facebook" Tencent má hodnotu přes 500 miliard dolarů

ČTK , 21. listopad 2017 08:00

Tencent je známý hlavně díky své mobilní aplikaci WeChat....

Více 1 komentářů

Starší zprávičky

Výrobce čipů Marvell kupuje za 6 mld. USD rivala Cavium

ČTK , 20. listopad 2017 14:57

Cavium využívá technologii ARM a snaží se narušit pozici Intelu na trhu mikroprocesorů pro servery....

Více 0 komentářů

Na trh přichází GFI MailEssentials 21

Pavel Houser , 20. listopad 2017 13:36

Nová verze posiluje úroveň bezpečnosti elektronické pošty pro SMB společnosti....

Více 0 komentářů

Prodej elektroniky i kancelářské techniky v ČR se zvýšil

Pavel Houser , 20. listopad 2017 13:28

Vývoj prodejů je dán mj. růstem cen desktopů, notebooků i inkoustových tiskáren....

Více 0 komentářů

Toshiba odvrací stažení akcií z burzy

ČTK , 20. listopad 2017 09:19

Správní rada podniku schválila zvýšení kapitálu na nedělním zasedání....

Více 0 komentářů