Metódy v bioinformatike - 06 - Zarovnávanie sekvencií (časť 2)

Zhrnutie prednášky

Prednáška nadväzuje na dynamické programovanie pre globálne a lokálne zarovnanie a upozorňuje, že jeho zložitosť úmerná n·m je pri celých genómoch neúnosná. Porovnanie ľudského a myšieho chromozómu s 100 miliónmi báz by trvalo približne 25 rokov. Preto zavádza heuristické lokálne zarovnanie, ktoré nezaručuje optimum, ale beží rýchlejšie. Najprv sa pomocou slovníka (indexu) krátkych podreťazcov dĺžky w nájdu presné zhody, tzv. jadrá zarovnania. Jadrá sa potom rozširujú a spájajú pozdĺž uhlopriečok matice. Náhodné zhody jadier sú však drahým a zbytočným krokom: ich očakávaný počet je n·m·4^(−w), takže voľba w je kompromisom medzi rýchlosťou a citlivosťou.

• - Dynamické programovanie so zložitosťou n·m je pre celé genómy príliš pomalé.
• - Heuristické zarovnanie je rýchlejšie, ale nezaručuje nájdenie najlepšieho zarovnania.
• - Dobré zarovnania zodpovedajú dlhým uhlopriečkam v matici dynamického programovania.
• - Presné zhody dĺžky w (jadrá) sa rýchlo nájdu cez slovník podreťazcov prvej sekvencie.
• - Drahým krokom je rozširovanie a spájanie jadier pozdĺž uhlopriečok.
• - Očakávaný počet náhodných zhôd je n·m·4^(−w); zníženie w o 1 ich zoštvornásobí.
• - Príliš malé w (napr. 2) vyrába veľa zbytočnej práce, príliš veľké w hrozí prehliadnutím skutočných zarovnaní.

Zhrnutie pripravené s pomocou AI z prepisu videa.