Bioinformatyka (przedmiot obieralny) − zadanie laboratoryjne

Wprowadzenie

Problemy sekwencjonowania łańcuchów DNA, z wykorzystaniem standardowych bibliotek oligonukleotydów o stałej długości i przy założeniu obecności odpowiednio błędów negatywnych lub pozytywnych w danych wejściowych, mogą zostać sformułowane następująco. Pojęcie "idealne spektrum" oznacza kompletny i bezbłędny zbiór słów o jednakowej długości l, które można wyodrębnić w sekwencji o długości n, gdzie l ≤ n.


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 słów z S.

Problem ogólny zakładający równocześnie obecność obu typów błędów (negatywnych i pozytywnych) w danych wejściowych może zostać sformułowany następująco.


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

Projekt realizowany na zajęciach laboratoryjnych podzielony jest na dwa etapy, każdy zakończony oddaniem sprawozdania. Pierwszy etap polega na teoretycznym opracowaniu metody heurystycznej rozwiązującej optymalizacyjny problem 3. Metoda ma działać w wielomianowym czasie. W sprawozdaniu, oprócz opisu metody, należy dodatkowo zamieścić rozważania, jak można by zwiększyć jakość generowanych rozwiązań w przypadku dodatkowej wiedzy, że instancja zawiera błędy tylko jednego typu (negatywne lub pozytywne, problemy 1 i 2).

Drugi etap polega na zaimplementowaniu i przetestowaniu opracowanej wcześniej heurystyki dla problemu 3. Testy należy przeprowadzić co najmniej na obowiązkowych zbiorach instancji testowych. Mile widziane dodatkowe testy na instancjach wygenerowanych we własnym zakresie, zwłaszcza trudnych; proszę wtedy zwrócić uwagę na to, żeby kolejność podawanych algorytmowi słów była przypadkowa (nie podpowiadała rozwiązania). W sprawozdaniu należy zamieścić wyniki testów (czas obliczeń i jakość wygenerowanego rozwiązania dla każdej z testowanych instancji, mogą być dodatkowo podane w postaci zagregowanej), porównanie działania heurystyki dla zbiorów testowych różniących się rodzajem zawartych błędów, wnioski obejmujące plusy i minusy zaproponowanego rozwiązania.

Projekt realizowany jest w grupach dwuosobowych, ewentualnie jednoosobowo. Program nie potrzebuje interfejsu graficznego, język implementacji dowolny. Sprawozdania należy oddawać wyłącznie na nośniku papierowym (wydrukowane bądź napisane odręcznie). Na ocenę wpłynie oryginalność i zaawansowanie metody, jakość generowanych rozwiązań oraz złożoność obliczeniowa algorytmu.

Terminy oddania sprawozdań i prezentacji programu

• Sprawozdanie 1: do 23 kwietnia 2025.
• Sprawozdanie 2: do 4 czerwca 2025.
• Prezentacja programu: najpóźniej na ostatnich zajęciach w semestrze.
  
  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). Zostanie wystawiona jedna ocena końcowa, bez ocen cząstkowych za poszczególne sprawozdania.