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

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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