Angelika Fedáková: Vyhľadávanie DNA sekvencií v reťazcovom grafe

Školiteľka

Bronislava Brejová

Názov

Vyhľadávanie DNA sekvencií v reťazcovom grafe

Stručný popis

Máme DNA vzorku a prístroj, ktorý z daného reťazca vytvorí čítania, ktoré sú oproti celému reťazcu krátke a pochádzajú z náhodných miest v reťazci. Na vstupe dostaneme graf týchto čítaní, ktorý nám podľa prekryvov jednotlivých čítaní hovorí, ktoré časti na seba pravdepodobne nadväzovali a tie dá do jednotlivých vrcholov. Následne pospája hranami tie vrcholy, ktoré by mohli ísť za sebou, ale nie je to isté, z dôvodu napr. opakovania častí v pôvodnej DNA, teda z jedného vrcholu môže ísť hrana do viacerých vrcholov. Ďalej dostaneme nejaký druhý DNA reťazec, a našou úlohou je zistiť, či v našom grafe pre daný reťazec existuje cesta, alebo ak neexistuje, nájsť ideálne cesty pre nejaké časti reťazca alebo nájsť cesty, ktoré sa na reťazec alebo jeho časti čo najviac podobajú (napr. na základe editačnej vzdialenosti).

Zimný semester

  • Spracovanie súborov a základné prefiltrovanie dát.
  • Nájdenie ciest pre konkrétny genóm, pričom filtráciu zatiaľ berieme do úvahy iba minimálne

    • Cieľ letného semestra

  • Algoritmus generalizovať pre zložitejšie genómy
  • Vytvoriť filtráciu dát a zefektívniť výber ciest v grafe

    • Zdrojový kód

    Report

    Výsledky