Algoritmikus kérdések a bioinformatikában

A tantárgy angol neve: Algorithmic Aspects of Bioinformatics

Adatlap utolsó módosítása: 2009. március 10.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

PhD képzés

szabadon választható tantárgy

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZD303   2/0/0/v 3  
3. A tantárgyfelelős személy és tanszék Dr. Csima Judit, Számítástudományi és Információelméleti Tanszék
4. A tantárgy előadója
Név:

 

Beosztás:

 

Tanszék, Int.:

 

Dr. Csima Judit

 

egyetemi docens

 

SZIT

 

Dr. Marx Dániel

 

tud. ösztöndíjas

 

SZIT

 

5. A tantárgy az alábbi témakörök ismeretére épít

Algoritmusok bonyolultsága, P, NP, NP-teljesség, Karp-redukció, közelítő algoritmusok, dinamikus programozás, véges automaták.

7. A tantárgy célkitűzése

A tárgy a bioinformatika algoritmikus világába nyújt bevezetést. A tárgy célja, hogy a hallgatók megismerjék a bioinformatika különböző területein jelentkező elméleti problémákat és matematikai modelleket. A félév során számos ilyen problémát vizsgálunk algoritmikus szempontból: áttekintjük az irodalomban szereplő alapvető algoritmusokat, közelítő algoritmusokat és bonyolultsági eredményeket.

A tárgy elsajátításához biológiai előismeretek nem szükségesek.

8. A tantárgy részletes tematikája

1. hét: Molekuláris biológiai alapok; Mintaillesztés véges automatával;

2. hét: Boyer-Moore algoritmus; véges automata használata a preprocesszálás során;   

3. hét: Szuffix-fák, szuffix-tömbök,

4. hét: Dinamikus programozási algoritmusok szekvenciaillesztésre globális és lokális verzióban, általánosított büntetőfüggvények,

5. hét: A többszörös illesztés algoritmikus bonyolultsága, közelítő algoritmusok a többszörös illesztésre;

6. hét: Fizikai feltérképezés: restrikciós enzimeket használó módszerek, a kapcsolódó algoritmikus problémák bonyolultsága, visszalépéses algoritmus a "partial digest" esetben;

7. hét: Hibridizációt használó módszer a fizikai feltérképezésre, hibridizációs mátrix, PQ-fák;

8. hét: Legrövidebb szuperszó probléma, bonyolultsága, közelítő algoritmusok;

9. hét: Genomok átrendeződése, matematikai modellek, előjeles és előjel nélküli permutációk rendezése;

10. hét: Szintenikus távolság meghatározása, Evolúciós fák meghatározása metrikus és ultrametrikus távolságon alapuló módszerekkel, Evolúciós fa meghatározása bináris tulajdonságok alapján;

11. hét: Haplotípus-meghatározás; a kapcsolódó algoritmikus probléma bonyolultsága;

12. hét: Fehérje-interakciós hálózatok vizsgálata, súlyozott k-hosszú utak keresése;

13. hét: RNS másodlagos szerkezetének előrejelzése, dinamikus programozási algoritmusok, sztochasztikus CF nyelvtanok;

14. hét: Molekulák térszerkezetét is figyelembe vevő mintaillesztési feladat, ennek bonyolultsága;

 


9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Előadás és házi feladatok

10. Követelmények

a. A szorgalmi időszakban: részvétel az órákon, a házi feladat beadása

b. A vizsgaidőszakban: szóbeli vizsga

          c. Elővizsga: lehetséges

11. Pótlási lehetőségek

 A tanulmányi és vizsgaszabályzatnak megfelelően.

A házi feladat pótlólag beadható a pótlási hét végéig.

12. Konzultációs lehetőségek

Fogadó órákon, illetve személyes egyeztetés alapján

13. Jegyzet, tankönyv, felhasználható irodalom

H. J. Böckenhauer- D. Bongartz: Algorithmic Aspects of Bioinformatics (Springer, 2007.)

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra28
Félévközi készülés órákra17
Felkészülés zárthelyire 
Házi feladat elkészítése5
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés40
Összesen90
15. A tantárgy tematikáját kidolgozta
Név:

 

Beosztás:

 

Tanszék, Int.:

 

Dr. Csima Judit

 

egyetemi docens

 

SZIT