Sestavljanje genoma iz odčitkov zaporedjaRezar, Matija (Avtor) Brodnik, Andrej (Mentor) genomsestavljanje genomateorija grafovde Bruijnov grafEulerjev obhodV grobem lahko postopek sestavljanja genoma opišemo kot iskanje Eulerjevih obhodov v de Bruijnovih grafih. V nalogi povzamemo teorijo podatkovnih struktur za predstavitev (de Bruijnovih) grafov in opišemo nekaj implementacij. Usmerjen graf G(V,E) lahko predstavimo kot množico urejenih parov vi → vj ∈ E. De Buijnovi grafi so definirani tako, da je mogopče sosede vozlišča izračunati iz oznake vozlišča, kar pomeni, da se lahko po grafu sprehajamo s pomočjo poizvedb o pripadnosti možici sosednosti. Množica povezav je lahko shranjena v slovarju. Slovar je lahko determinističen, kot sta na primer drevo ali kazalo FM, ali osnovan na verjetnosti, kot sta na primer razpršilna tabela ali Bloomov filter. V delu predstavljamo kBWT, novo deterministično podatkovno strukturo za predstavitev de Bruijnovih grafov, ki uporablja skoraj optimalnih n · σ + o(n) bitov pomnilnika, kjer je n število k-merov v grafu in σ velikost abecede. Podatke o sosednjosti vozlišča lahko v njej najdemo v Θ(σ · k) časa. Strukturo primerjamo z obstoječo podatkovno strukturo ogrodja GATB, ki je osnovana na Bloomovih filtrih. Preizkusi kažejo, da je deterministični kBWT pričakovano počasnejši od podatkovne strukture ogrodja GATB. Pokazalo pa se je, da kBWT bolj učinkovito izrablja predpomnilnik, vendar to ni nadomestilo porabe procesorskega časa.20162017-03-27 13:06:13Magistrsko delo/naloga91246VisID: 17386sl