Dinamikus programozás Szekvenciaillesztés lineáris és tetszőleges résbüntetéssel. Gotoh algoritmusai affin és konkáv résbüntetésekre. Lokális szekvencaillesztés. Hierschberg algoritmus. A többszörös szekvenciaillesztési feladat, stratégiák, sum-of-pairs értékelés és annak NP-nehéz volta.
A legtakarékosabb fa problémája, multiway cut fákra, a Russel-Sankoff algoritmus. Nussinov algoritmusa maximális párosodásra álcsomó-mentes RNS térszerkezetekben. Transzformációs nyelvtanok Chomsky hierarchiája. Sztochasztikus reguláris nyelvtanok. Viterbi, Forward és Backward algoritmusok. Expectation Maximization. Az EM iterációban a likelihood monoton növekszik. A tropikus félgyűrű. A Viterbi algoritmus a Forward
algoritmus tropikalizációja. A Chomsky Normal Form. Minden sztochasztikus környezetfüggetlen nyelvtan valószínűségtartóan átí rható CNF-be. A
CYK, Inside és Outside algoritmusok, Expectation Maximization. Algebrai dinamikus programozás, yield grammar, evaluation grammar, hatékony implementáció objektumorientált programozási nyelvekben. Alkalmazások CpG szigetek keresése genomokban. Génkeresés. Fehérjék másodlagos térszerkezetének predikciója. A Knudsen-Hein nyelvtan, RNS-ek térszerkezetének predikciója. Genomátrendeződés. A dupla vágás és kötés model. A Hannenhalli-Pevzner elmélet: előjeles permutációk legtakarékosabb rendezései reverziókkal . Hierarchikus klaszterezés, evolúciós fa építés Ultrametrika, hierarchikus klaszterezés, UPGMA. Additív metrika, Neighbor Joining algoritmus. Karakter alapú faépítés, a nagy parszimónia probléma NP-nehéz. Adott fokszámsorozatot realizáló egyszerű, páros, irányított gráfok. Havel-Hakimi algoritmus. Bevezetés a
Markov lánc Monte Carlo módszerekbe: a Metropolis-Hastings algoritmus. Gibbs sampling. Parallel Tempering, Simulated Annealing . Példák alkalmazásokra. Tételek Markov láncok konvergenciasebességére. A mintavételezések bonyolultságelméleti alapjai: bonyolultsági osz tályok. Híres nehéz approximálható problémák.