Teaching

Plik dmel-4-r5.47.gff zawiera anotacje chromosomu 4 muszki owocowej. Każda linijka stanowi pojedynczy wpis – rekord, składający się z kilku pól, m.in. nazwy chromosomu (kolumna 0), typu rekordu i spełnianej w ramach tego typu roli (kolumny 1 i 2), początkowej i końcowej pozycji wpisu (liczby całkowite, w tysiącach par zasad – kolumny 3 i 4), opcjonalnie wartości odczytu (tzw. score, kolumna 5), znaku nici DNA, której dotyczy wpis (+ lub -, kolumna 6) i deskryptora (kolumna 8).

1. (3p.) Napisz funkcję score(f_in, f_out, x), która dla zadanego parametru x znajduje w pliku f_in rekordy typu DGIL_snap (rola match_part) o score, którego wartość bezwzględna jest większa niż x. Rekordy spełniające te warunki powinny zostać posortowane według malejącej wartości bezwzględnej score. Wynik ma mieć postać
   p_1 k_1 s_1
   p_2 k_2 s_2
   …
   (wartości oddzielane spacjami, nowa linia po każdym wierszu, p_i i k_i oznaczają odpowiedznio początkową i końcową pozycję i-tego wpisu, a s_i oznacza wartość score (nie wartość bezwzględną, po której sortujemy – znak ma pozostać!). Wynik powinien zostać zapisany do pliku f_out.
   Jako wynik, oprócz kodu programu należy przysłać plik wynik1.txt, stanowiący efekt wywołania funkcji score(“dmel-4-r5.47.gff”, “wynik1.txt”, 20).
2. (3p.) Wyszukaj wszystkie rekordy z pliku dmel-4-r5.47.gff typu OrthoDB (rola orthologous_to), podziel je wg gatunków, w których występują ortologiczne geny (wartośc po “to_species”; np. Dper, Dmel, Cele, Dyak, Drer, …) i dla każdego gatunku wypisz plik w formacie gff (możesz skopiować całe linijki z pliku wejściowego) zawierający tylko rekordy, w których ortologiczne fragmenty leżą na tej samej nici (ostatnia i 7. kolumna zawierają ten sam znak) co w Dmel. Dla każdego z gatunków plik nazwij “nazwa_gatunku.gff”, np. “Dper.gff”.
3. (4p.) Wyszukaj w pliku dmel-4-r5.47.gff promotorów (rekordy typu promoter, rola match), które nie należą do żadnego obszaru 5′ Untranslated Transcribed Region (rola five_prime_UTR). Wypisz do pliku wynik3.gff wszystkie rekordy zawierające takie promotory (całe linijki).

Zadania w postaci kodu źródłowego (w jednym pliku zadanie1_nr-indeksu.py) i plików wynikowych (załączniki z rozszerzeniem .txt lub .gff, żadnych kompresji itp.) przesyłają Państwo do obu prowadzących ćwiczenia (bartek@mimuw.edu.pl i pawel.bednarz@mimuw.edu.pl) przed wykładem za dwa tygodnie (26. XI 2012, 12:15). Proszę o umieszczenie w tytule e-mail’a hasła [WDI-1] i o wysyłanie ze skrzynek studenckich (aby łatwiej było zidentyfikować autora i ew. “zapożyczenia”).

Slajdy z wykładu tu

1. W pliku HP1b.gff3 znajdują się dane o miejscach wiązania białka HP1b do nici DNA muszki owocowej. Znajdź średnią wartość sygnału dla chromosomu 2L na pozycjach od 1,000,000-5,000,000.
2. W pliku DNA.txt znajduje się fragment nici DNA człowieka. Znajdź listę wszystkich wystąpień sekwencji ACGT.
3. Używając maksymalnie trzech wywołań funkcji strip, rstrip, lstrip przejdź od:
   • abcccbca do ccc
   • bababa do ab
4. Zastąp spacje przez myślniki w napisie “Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc sit amet ligula in nisi varius mattis nec a urna. Phasellus tristique vehicula elit id imperdiet. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc orci libero, accumsan quis cursus vel, pretium nec dui. Nunc lobortis mollis felis, at malesuada velit volutpat id. Pellentesque quis iaculis massa. Vestibulum commodo egestas fringilla. Proin quis justo nunc. Nam sed ultricies orci. Curabitur adipiscing, dolor vel rhoncus accumsan, sapien tellus volutpat eros, at luctus mi augue sit amet turpis. Aliquam sagittis, lacus id commodo volutpat, erat justo auctor massa, in faucibus quam lectus et libero. Curabitur laoreet risus in urna aliquet vel fringilla felis volutpat. Morbi suscipit purus velit.” używając
   • funkcji replace
   • funkcji split i join
5. *K-merami nazywamy sekwencje DNA długości k. Dla pliku DNA.txt wypisz najczęściej występujący 4-mer.
   Wskazówki:
   • stwórz funkcję, która dla danego k-meru znajdzie następny w stosunku do niego k-mer (w porządku leksykograficznym)
   • iterując po kolejnych 4-merach (począwszy od “AAAA”) znajdź liczbę ich wystąpień (używając funkcji z zadania 2); zapamiętaj najwyższy wynik i odpowiadający mu 4-mer

Powtórka przed kolokwium

Zadania na rekurencję:

1. Napisz rekurencyjną funkcję triangle(n), generującą dla zadanego n wzory postaci:

   ****
   ***
   **
   *
   

   o n liniach.

2. Weźmy funkcję f zdefiniowaną następująco:

   def f(n):
       if n % 2 == 0:
           return n / 2
       else:
           return 3*n + 1
   

   Napisz rekurencyjną funkcję collatz_steps(n), która zwróci dla zadanego n liczbę elementów ciągu n, f(n), f(f(n)), …, potrzebnych do osiągnięcia 1. Np.

   collatz_steps(1) == 0
   collatz_steps(4) == 2
   

3. Napisz rekurencyjną funkcję binary(n), która dla zadanej liczby n znajdzie jej zapis binarny.
   Wskazówka: ostatnią cyfrą w tym zapisie będzie n % 2.
4. Napisz rekurencyjną funkcję newton(n, k), która dla zadanych liczb n i k wylicza współczynnik dwumianowy (“n po k”, wzór rekurencyjny na stronie http://pl.wikipedia.org/wiki/Symbol_Newtona).
5. Załóżmy, że mamy daną funkcję rosnącą w przedziale <0;n>. Napisz rekurencyjną funkcję bisection(f), która znajdzie przybliżenie miejsca zerowego funkcji f.

   Wskazówka 1: funkcję f można zdefiniować np. tak:

   def f(x):
   	import math
   	return math.tan(x - math.pi)
   

   i dalej wywołać funkcję bisect na funkcji f: bisect(f)
   
   Wskazówka 2: zastosuj metodę “połowienia” przedziału <0;n> – podobnie jak to miało miejsce w przypadku wyszukiwania binarnego.

6. Napisz rekurencyjną funkcję rec_count(v, x), która dla listy v i liczby x zwróci liczbę wystąpień liczby x w liście v.
7. Napisz rekurencyjną funkcję find_sum(v, x), która sprawdzi, czy na liście v występują dwie kolejne liczby o sumie x.
8. Napisz rekurencyjną funkcję check_sort(v), która sprawdzi, czy lista v jest posortowana.
9. Napisz rekurencyjną funkcję rev_number(n), która dla danej liczby całkowitej n zwróci liczbę powstałą z n poprzez odwócenie porządku cyfr (np. rev_number(123)=321). Uwaga: chodzi o rozwiązanie używające wyłącznie operacji na liczbach całkowitych.
10. Napisz rekurencyjną funkcję strange_sum(n), która zwróci sumę kwadratów liczb parzystych mniejszych lub równych niż n i sześcianów liczb nieparzystych mniejszych lub równych niż n (np. strange_sum(3) = 1 + 4 + 27 = 32.

Zadania wg. P. Bednarza

1. używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować i wypisać (Tutaj przyda się iteracyjna wersja merge)
2. Co robi funkcja f?

   			def f(a, b):
   				if b == 0:
   					return 0
   				return a + f(a, b - 1)
   			

3. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
4. Co zwracają funkcje e i o zdefiniowane poniżej?

   			def e(n):
   				if n == 0:
   				        return True
   			        else:
   				        return o(n - 1)
   
   			def o(n):
   				if n == 0:
   				        return False
   				else:
   				        return e(n - 1)
   			

5. Co zwracają funkcje take i skip zdefiniowane poniżej?

   			def take(l):
   				if l == []:
   					return []
   				else:
   					return [l[0]] + skip(l[1:])
   			def skip(l):
   				if l == []:
   					return []
   				else:
   					return take(l[1:])
   			

6. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
7. Napisz rekurencyjną funkcję rec_find(v, x), która zadanego posortowanej listy v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False.
8. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
9. Podziałem liczby naturalnej n nazwiemy ciąg liczb naturalnych sumujących się do n. Napisz rekurencyjną funkcję partition(n), która znajdzie wszystkie podziały liczby n.

Dziś będzie o rekurencji. Slajdy tu, kod z wykładu tam