Otázka:
Pochopení inicializace algoritmu Needleman-Wunsch
Heeh wei cheng
2018-12-06 08:18:14 UTC
view on stackexchange narkive permalink

Chtěl bych se zeptat, proč když inicializujeme 0 jako výchozí bod, existují 3 šedé rámečky, které se nepoužívají, jak je znázorněno (zvýrazněno červeným rámečkem) na obrázku? pic of matrix Mají tato pole ukázat, že se jedná o mezery, nebo je jen správně zarovnat?

Také bych se chtěl zeptat, jak hraje dynamické programování roli při vyplňování řádků a sloupců v matici. (Jsem v bioinformatice nováčkem)
Vítejte na stránkách Heeh. Svou otázku můžete [upravit] a přidat k ní věci, například další informace. Mohli byste objasnit, co máte na mysli pod pojmem „jak hraje roli dynamické programování“? Chcete vědět, co je dynamické programování? Nebo proč je pro tento algoritmus potřeba?
Ahoj, chtěl bych vědět jak o dynamickém programování, tak o tom, proč je pro tento algoritmus potřebný. Hledal jsem význam dynamického programování, ale nerozumím významu rekurzivního.
Jeden odpovědět:
llrs
2018-12-06 17:48:35 UTC
view on stackexchange narkive permalink

První sloupec je přidán, aby bylo možné zarovnat sekvence. Mohly by to být mezery, pokud zarovnání skončí počínaje v různých pozicích než první. Bez prvního prázdného řádku a sloupce by nebylo možné mít mezery na začátku zarovnání.

Dynamické programování je užitečné, protože je třeba nejprve vypočítat skóre pro každou pozici, a jakmile získáte skóre, můžete vypočítat optimální cestu. Váš problém tedy vyřešíte tak, že nejprve spočítáte, co by se stalo, kdyby (byla tam mezera, došlo k nesouladu ...) a pak najdete optimální zarovnání.

Dynamické programování není nezbytně nutné, ke zpracování řádků je vhodné pouze použít rekurzi (v závislosti na implementaci můžete také ušetřit paměť tím, že neukládáte celou matici).


Tyto otázky a odpovědi byly automaticky přeloženy z anglického jazyka.Původní obsah je k dispozici na webu stackexchange, za který děkujeme za licenci cc by-sa 4.0, pod kterou je distribuován.
Loading...