Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

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

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.

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;

Előadás és házi feladatok

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

 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.

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

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