Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE91AM53
Tantárgy azonosító adatok
1. A tárgy címe Bioinformatika
2. A tárgy angol címe Bioinformatics
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 v Kredit 2
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1 BMEVISZAB01 AlgoritmusElm BMETE95AM31 Statisztika 1
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Algebra Tanszék
7. A tantárgy felelős oktatója Dr. Miklós István beosztása Tudományos munkatárs
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2015.02.16. Akkreditációs bizottság döntési időpontja 2016.04.18.
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
valószínűségszámítás alapfogalmai
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
TTK Matematika (BSc) képzés Adattudományi sávjának kötelezően választható tárgya.
11. A tárgy részletes tematikája
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.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 részvétel az előadásokon vizsga-
időszakban		 vizsga
13. Pótlási lehetőségek
TVSZ szerint
14. Konzultációs lehetőségek
TVSZ szerint
15. Jegyzet, tankönyv, felhasználható irodalom
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
28
16.2 Félévközi felkészülés órákra
14
16.3 Felkészülés zárthelyire
0
16.4 Zárthelyik megírása
0
16.5 Házi feladat elkészítése
0
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
0
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
18
16.9 Összesen
60
17. Ellenőrző adat Kredit * 30
60
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Miklós István
tudományos munkatárs
Matematikai Kutatóintézet
A tanszékvezető
19. Neve aláírása
Dr. Nagy Attila