Bioinformatyka (przedmiot obieralny) - laboratorium

semestr letni 2011/2012

Problem 1: Sekwencjonowanie łańcuchów DNA z błędami negatywnymi

Instancja: Zbiór S słów o jednakowej długości l nad alfabetem {A, C, G, T}, długość n sekwencji oryginalnej, przy czym S jest podzbiorem idealnego spektrum dla tej sekwencji.
Odpowiedź: Sekwencja o długości nie większej niż n zawierająca wszystkie słowa z S.

Problem 2: Sekwencjonowanie łańcuchów DNA z błędami pozytywnymi

Instancja: Zbiór S słów o jednakowej długości l nad alfabetem {A, C, G, T}, długość n sekwencji oryginalnej, przy czym S jest nadzbiorem idealnego spektrum dla tej sekwencji.
Odpowiedź: Sekwencja o długości n zawierająca n-l+1 różnych słów z S.

Problem 3: Sekwencjonowanie łańcuchów DNA z błędami negatywnymi i pozytywnymi

Instancja: Zbiór S słów o jednakowej długości l nad alfabetem {A, C, G, T}, długość n sekwencji oryginalnej.
Odpowiedź: Sekwencja o długości nie większej niż n zawierająca maksymalną liczbę słów z S.

Zadanie

Należy dla problemów 1 i 2 opracować i zaimplementować heurystyki działające w czasie wielomianowym. Heurystyki mają być specjalizowane, tzn. dostosowane do właściwości konkretnego problemu w celu optymalizacji jakości otrzymywanych rozwiązań. Dodatkowo należy opracować i zaimplementować bardziej ogólną heurystykę działającą w czasie wielomianowym i rozwiązującą problem 3. Szczegóły pozostawione są każdej z grup do indywidualnej realizacji. Na ocenę wpłynie oryginalność i zaawansowanie metod, jakość generowanych rozwiązań oraz złożoność obliczeniowa algorytmów. Jakość generowanych rozwiązań będzie mierzona odległością liczby słów z S w rozwiązaniu od wartości optymalnej (którą jest dla problemów 1, 2 i 3 odpowiednio |S|, n-l+1 i min{|S|, n-l+1}); ograniczenie na długość sekwencji musi pozostać nienaruszone. Testy należy przeprowadzić co najmniej na obowiązkowych zbiorach instancji testowych. W testach należy porównać parami algorytmy specjalizowane z ogólnym (tzn. algorytm dla problemu 1 z algorytmem dla problemu 3 oraz algorytm dla problemu 2 z algorytmem dla problemu 3) i spodziewane są lepsze wyniki dla algorytmów specjalizowanych. Mile widziane dodatkowe testy na instancjach wygenerowanych we własnym zakresie, zwłaszcza trudnych.

W sprawozdaniach z realizacji zadań należy zamieścić opis metod, wyniki testów (czas obliczeń i jakość generowanych rozwiązań, porównanie z heurystyką ogólną), wnioski obejmujące plusy i minusy zaproponowanego rozwiązania. Sprawozdanie dla problemu 1 obejmuje opis metody dla problemu 3. Sprawozdania należy oddawać wyłącznie na nośniku papierowym (wydrukowane bądź napisane odręcznie).

Terminy oddania programów i sprawozdań

• Problem 3 - termin prezentacji programu: najpóźniej na zajęciach w dniu 11 kwietnia 2012. Prezentacja programu nie wiąże się z oddaniem sprawozdania i dopuszczone jest wprowadzenie późniejszych poprawek (aż do oddania sprawozdania dla problemu 1), ale pokazany program musi działać i rozwiązywać problem 3.
• Problem 1 - termin oddania sprawozdania: najpóźniej w dniu 24 kwietnia 2012.
• Problem 1 - termin prezentacji programu: najpóźniej na zajęciach w dniu 25 kwietnia 2012.
• Problem 2 - termin oddania sprawozdania: najpóźniej w dniu 29 maja 2012.
• Problem 2 - termin prezentacji programu: najpóźniej na zajęciach w dniu 30 maja 2012.
  
  Każdy tydzień spóźnienia w stosunku do podanych powyżej terminów skutkuje obniżeniem oceny o kolejne 0,5 stopnia (do granicy 3,0 w przypadku wystawienia oceny pozytywnej; ew. obniżenie za problem 3 wchodzi w ocenę za problem 1). Ocena końcowa będzie średnią z dwóch wystawionych ocen, za rozwiązanie problemów 1 i 2.
  

Konsultacje

W semestrze letnim 2011/2012: środy 9:45-11:15, p. 2.6.3 BT.