MiASD/L/z2

From WikiZMSI

< MiASD | L
[edytuj]

Na zajęciach

Problem (Motif / Median String Search): Dany jest zbiór t sekwencji DNA, każda o długości n, oraz zadana jest długość l poszukiwanego motywu. W sekwencjach ukryty jest motyw regulatorowy (w każdej sekwencji jedno wystąpienie), tj. napis o długości l, który w poszczególnych sekwencjach może objawiać się w nieco innej odsłonie (drobne zaburzenia / mutacje). Należy wykryć motyw - podać jego wersję reprezentatywną (median string).

Przykład: t = 8, l = 10, n = 64

DNA:

{"ctgtagagcgactatttaggtggaccaaaactgttcctggccctcataactaaccagttcctcc",

"caaggttcatggatcggactgcatcgctaacccgacactgtaaaacagaggcggctcactcttt",

"tgacatctacaatgggaaattttagggagtcgtttggaagctaaccagggtcccagtcttcaaa",

"atttactaaggtggggagtaatttatctatctccgttgtgcttaaatcgatctatgccttgaat",

"gttcaacaccgtcgatgagtgtaagttgcctatctaaatctcacacctgttcaccaggcaagct",

"taaaaaattacattctctcaccaggtcgacaacgtcgccgaatagccacccagggtaaatcgca",

"gctagtccaaggaaaacccgaaccgagggaggccaaccaggtgtggcagaaatgcaacggtctt",

"attcctgatcccctaggtcatccattacagaagactaacctggacgtggtgatgtaacggttct"}


Rozwiązanie:

motyw (median string): "gctaaccagg"

osadzenie motywu w zbiorze sekwencji (wielkie litery):

{"ctgtagagcgactatttaggtggaccaaaactgttcctggccctcataACTAACCAGTtcctcc",

"caaggttcatggatcggactgcatcGCTAACCCGAcactgtaaaacagaggcggctcactcttt",

"tgacatctacaatgggaaattttagggagtcgtttggaaGCTAACCAGGgtcccagtcttcaaa",

"atttACTAAGGTGGggagtaatttatctatctccgttgtgcttaaatcgatctatgccttgaat",

"gttcaacaccgtcgatgagtgtaagttgcctatctaaatctcacacctGTTCACCAGGcaagct",

"taaaaaattacattctctcaccaggtcgacaacgtcgccgaataGCCACCCAGGgtaaatcgca",

"gctagtccaaggaaaacccgaaccgagggagGCCAACCAGGtgtggcagaaatgcaacggtctt",

"attcctgatcccctaggtcatccattacagaagACTAACCTGGacgtggtgatgtaacggttct"}


Wskazówki:

  • Zapoznać się z funkcjami IToB oraz BToI, które konwertują ciągi liczb całkowitych do napisów z zasadami (a, c, g, t) i w drugą stronę.
  • Zapoznać się z funkcją FakeData generującą losowe sekwencje DNA wraz ze "wstrzykniętym" do nich zadanym motywem. Zaburzenia motywu będą generowane wg podanego jako argument prawdopodobieństwa mutacji na poziomie pojedynczej zasady.
  • Zapoznać się z funkcjami do przechodzenia drzewa przeszukiwań: NextVertex i ByPass, oraz ich wersjami skompilowanymi NextVertexC i ByPassC.
  • Zaprogramować algorytm typu "branch and bound" do poszukiwania napisu medianowego. Algorytm na wejście powinien otrzymywać zbiór sekwencji DNA oraz liczbę l (długość poszukiwanego motywu). Na wyjściu algorytm powinien zwracać napis medianowy. Implementację warto rozpocząć od napisania funkcji pomocniczej obliczającej odległość Hamminga pewnego słowa (lub prefixu) od zbioru sekwencji DNA (funkcja TotalDistance z wykładów). W funkcji pomocniczej warto wykorzystać istniejącą w Mathematica funkcję HammingDistance oddającą odległość Hamminga dwóch ciągów.
[edytuj]

Do domu

  • Przepisać funkcję TotalDistance na wersję skompilowaną TotalDistanceC i używać jej w algorytmie "branch and bound".
  • Dla kilku eksperymentów porównać czasy wykonań alogorytmu używającego nieskompilowanej (TotalDistance) vs. skompilowanej (TotalDistanceC).
  • Do algorytmu dodać licznik odwiedzonych węzłów w drzewie i zwracać go jako dodatkowy wynik. Po wykonaniu przeszukiwania obliczyć, jaki procent całego drzewa (wszystkich węzłów) odwiedził algorytm.
Źródło: "http://wikizmsi.zut.edu.pl/wiki/MiASD/L/z2"