Laboratorium Bioinformatyki - kierunek Informatyka, 6 semestr, grupa L10 (piątkowe zajęcia o 8:00).

Informacje dotyczące przerwy w prowadzeniu zajęć z powodu epidemii SARS-CoV-2.

Dwa  początkowe spotkania prowadzone są przez dr Agnieszką Żmieńko, pierwsze się odbyły, drugie niestety wypadły. Z zajęć prowadzonych przeze mnie wypadną co najmniej trzy, co nie powinno stanowić problemu. Sytuacja jednak może się zmienić i w związku z tym proponuje zapoznać się z przygotowanymi materiałami, oraz materiałami profesor Marty Kasprzak prowadzącej wykłady.

Proszę również o kontakt osoby uczestniczące w moich zajęciach, mój adres mailowy to This email address is being protected from spambots. You need JavaScript enabled to view it.. Proszę dobrać się w dwuosobowe zespoły i wybrać problem do rozwiązania, szczegóły na pierwszym spotkaniu.

Proszę obserwować również tą stronę, będą tu umieszczać kolejne materiały związane z zajęciami.

W ramach zajęć zdalnych proponuję spotkania na platformie Zoom, zapisane spotkania będą dostępna na YouTube:

2020-03-20 8:00 Wprowadzenie

2020-03-27 10:00 Definicja problemu

2020-04-03 10:00 Algorytm dokładny

2020-04-17 10:00 Algorytmy heurystyczne

2020-04-24 10:00 Podejścia nieklasyczne

2020-05-08 10:00 Bioinformatyka L10 - omówienie BSBH-

2020-05-15 10:00 Bioinformatyka L10 - omówienie RSBH+

2020-05-22 10:00 Bioinformatyka L10 - omówienie PSBH-

2020-05-29 10:00 Bioinformatyka L10 - omówienie PSBH+

2020-06-05 10:00 Bioinformatyka L10 - omówienie ALT-

 

W celu przeprowadzenia ćwiczenia przed rozwiązaniem właściwego problemu polecam rozwiązanie podstawowej wersji problemu na platformie HackerRank

DNA sequencing by hybridization

W celu zaliczenia ćwiczenia wymagane jest przejście wszystkich czterech przykładów, ponadto przewidziałem nagrody w postaci ocen:

5
dla najlepszej osoby
4,5
dla pozostałych miejsc na podium
4
dla miejsc 4-6
3,5
dla osób których algorytmy rozwiążą ponad 10 testów
3
dla osób, których rozwiązanie zadziała dla wszystkich czterech przykładów (musi to być jednak algorytm).

Brak rozwiązania do końca kwietnia skutkować będzie niezaliczeniem tego ćwiczenia, co będzie rzutować na ocenę końcową.

 

 

Z powodu przedłużającego się okresu zajęć zdalnych proponuję kolejne zadania w HackerRank:

DNA sequencing by hybridization MEGA

Tym razem do końca maja, oceny dla każdego osobnego wyzwania (chalenge) tak samo jak dla poprzedniego wyzwania.

Jako dodatkowy bonus, osoba która zwycięży całe zawody (contest) i spełni pozosałe minimalne wymagania (jak zaliczenie projektu), otrzyma ocenę 5 na zaliczenie laboratorium.

 

Uwaga: HackerRank ma ograniczenia czasowe i pamięciowe na rozwiązania, największe instancje mogą się nie zmieścić w ograniczeniach.

Ograniczenia te są różne dla różnych języków, we wszystkich pozostawiłem domyślne wartości.

 

Materiały dla zajęć laboratoryjnych:

Bioinformatyka-wprowadzenie.pdf

Bioinformatyka-SBH-definicja problemu.pdf

Bioinformatyka-SBH-algorytm-dokładny.pdf

Bioinformatyka-SBH-algorytmy-heurystyczne.pdf

Bioinformatyka-SBH-podejścia-nieklasyczne.pdf

Zajęcia polegają na pracy w dwuosobowych grupach. Każda grupa przygotowuje algorytm dokładny oraz heurystyczny rozwiązujący jeden (każda grupa wybiera inny problem) z następujących problemów sekwencjonowania przez hybrydyzację:

  1. Sekwencjonowanie w oparciu o chipy binarne , z błędami negatywnymi : Binary Chip Err-
  2. Sekwencjonowanie w oparciu o chipy binarne , z błędami pozytywnymi : Binary Chip Err+
  3. Sekwencjonowanie z informacją o powtórzeniach , z błędami negatywnymi : Repetition SBH Err-
  4. Sekwencjonowanie z informacją o powtórzeniach , z błędami pozytywnymi : Repetition SBH Err+
  5. Sekwencjonowanie z informacją o położeniu , z błędami negatywnymi : Position SBH Err-
  6. Sekwencjonowanie z informacją o położeniu (poprzednia wersja), z błędami negatywnymi : Position SBH Err-
  7. Sekwencjonowanie z informacją o położeniu , z błędami pozytywnymi : Position SBH Err+
  8. Sekwencjonowanie z informacją o położeniu (poprzednia wersja), z błędami pozytywnymi : Position SBH Err+
  9. Sekwencjonowanie w oparciu o chipy alternatywne , z błędami negatywnymi : Alternating Chip Err-
  10. Sekwencjonowanie w oparciu o chipy alternatywne , z błędami pozytywnymi : Alternating Chip Err+

Podział na grupy:

1. Bin - : 136715 136705

2. Bin + : wolny

3. Rep - : wolny

4. Rep + : 132211 136713

5. Pos - : 136740 136746

6. Pos + : 136682 136573

7. Alt - : 136745 136834

8. Alt + : wolny

Poza przygotowaniem algorytmów rozwiązujących wybrany problemu, należy przygotować sprawozdanie z ich opisem, oraz analizą działania programu (przykładowo zależność czasowa od długości instancji wejściowej, oraz od ilości błędów).

Pobranie instancji testowej: www.piotr.e.wawrzyniak.doctorate.put.poznan.pl/bio.php, parametry

n
długość sekwencji, zakres 16 - 65536
k
długość sondy, zakres 4 - 10, nukleodyty uniwersalne nie są wliczane do długości, nukleodyty binarne liczone są jako ½
mode
typ sondy, jedna z wartości: basic, gapped, alternating lub binary
intensity
wartość binarna, dla true zwraca informację o intensywności odczytu, wartość ta jest zależna (nieliniowo!) od liczby sparowanych oligonukleotydów
position
wartość binarna, dla true zwraca zakres położeniu oligonukleotydu, w przypadku więcej niż jednego wystąpienia w sekwencji jest to informacja o ostatnim dopasowanym oligonukleotydzie
wartość old zwraca wartość w postaci przedziału
sqpe | sqpep
Liczba błędów pozytywnych, sqpe liczbowo, sqpep procentowo, wartość ≤ n⁄4
sqne | sqnep
Liczba błędów negatywnych, sqne liczbowo, sqnep procentowo, wartość ≤ n⁄4
pose | posep
Szerokość przedziału ufności dla informacji o położeniu, dla starego trybu (position=='old') liczba błędów w informacji o położeniach, pose liczbowo, posep procentowo, wartość ≤ n⁄2