WYKŁAD 1, 23/02/2012
Wstęp do bioinformatyki
Bioinformatyka jest dyscypliną pomocniczą biologii, gałęzią biologii teoretycznej. Zajmuje się wykorzystaniem komputerów do wspomagania prowadzenia badań w wielu dziedzinach biologii, np.
· taksonomii
· biologii molekularnej
· biochemii
· biofizyki
Wspomaganie to polega na gromadzeniu, udostępnianiu i przetwarzaniu danych różnego typu. Przetwarzanie zgromadzonych danych może prowadzić do nowych odkryć, należy jednak pamiętać, że bioinformatyka umożliwia predykcje, które muszą być zawsze zweryfikowane doświadczalnie.
Systemy linuksowe dzielą się na kilka rodzajów, w zależności od sposobu „pakietowania” oprogramowania:
· systemy „redhatopodobne”: pakiety rpm, np. Fedora, RedHat Enterprise Linux, Suse, CentOS, PLD
· systemy „debianopodobne”: pakiety deb, np. Debian, Ubuntu, Xubuntu, Kubuntu itp.
· systemy kompilowane: wszystkie programy kompilowane ze źródeł, np. Gentoo, Linux from scratch
· Slackware – dystrybucja oparta o pakiety tzg
Obsługa linuksa w trybie graficznym:
· praca z systemem linuksowym w trybie graficznym nie różni się zasadniczo od pracy w Windowsie
· w linuksie nie da się pracować bez zalogowania – podania loginu i hasła
· popularne skróty klawiaturowe działają tak samo
· wygląd może się dosyć mocno różnić w zależności od używanych programów i ustawień
· programy windowsowe nie działają z zasady w innych systemach, dlatego pod linuksem używa się programów spoza Microsoft
Oprogramowanie pod linuksem:
· programy potrzebne do pracy z komputerem dostępne są dla każdego użytkownika za darmo
· w większości systemów instalacje są automatyczne, nie trzeba się martwić zakupem licencji i instalacją osobnych programów
· niektóre wysoce specjalistyczne programy występują wyłącznie w wersji dla Windows (np. CorelDraw, AutoCAD)
· niektóre bioinformatyczne narzędzia występują wyłącznie pod linuksem
· pakiet biurowy – OpenOffice
Bazy danych
Zasoby informacji na temat organizmów i procesów w nich zachodzących można podzielić na kilka kategorii:
· sekwencje nukleotydowe i białkowe
· mapy genetyczne i fizyczne
· struktury białek i innych molekuł
· literatura
· informacje o ekspresji genów
Trzy główne ośrodki gromadzonych danych sekwencyjnych to:
· NCBI (National Center of Biological Information) w USA
· DDBJ (DNA Data Bank of Japan) w Japonii
· EMBL (European Molecular Biology Laboratory) w Europie
Te trzy ośrodki prowadzą zsynchronizowane bazy danych – informacje zgłoszone w jednej z nich zostaną wprowadzone do wszystkich trzech.
Bazy sekwencji:
· aby informacje o sekwencji genomów i białek gromadzone w bazach danych były użyteczne, dane muszą być przechowywane w odpowiedniej formie, łatwej do przetwarzania komputerowego, a jednocześnie do czytelnej prezentacji ludzkiemu użytkownikowi
· wymaga to określenia odpowiedniego modelu danych, czyli formalnego sposobu ich opisu; informacje, jakie należy uwzględnić to m.in.
- pozycja systematyczna organizmu, z którego pochodzi sekwencja
- rodzaj cząsteczki (DNA, RNA, białko)
- rodzaj sekwencji (genomowa, plazmidowa, sztucznie stworzony wektor)
- autor
- unikalny numer sekwencji
· ponieważ najczęściej nie wyciągamy z bazy rekordów, gdzie jakieś pola mają określoną wartość, tylko takie, gdzie pole „sekwencja” ma zawartość podobną do sekwencji, którą poszukujemy (sekwencji kwerendowej), standardowy model relacyjnej bazy danych nie jest odpowiedni
· przeszukiwanie olbrzymich baz danych wymaga użycia algorytmu heurystycznego, takiego, jak zaimplementowany w programie BLAST; takie programy mają różne wymagania co do formatu bazy danych, np. BLAST wymaga odpowiedniego przygotowania bazy (sformatowanie jej programem formatdb)
· najczęściej w bazach danych rekordy są przechowywane w plikach binarnych; w przypadkach baz sekwencyjnych korzysta się raczej z formatu tekstowego (plain text)
· poszczególne rekordy są wyróżnionymi częściami jednego, dużego pliku tekstowego; dane w takim pliku są opisywane przy użyciu języka ASN1, a następnie program umożliwiający dostęp do bazy interpretuje odpowiedni rekord i wyświetla go w wybranym, czytelnym dla człowieka formacie
· może to być np. Fasta (inaczej format Pearsona) lub GenBank
Numery dostępu:
· każda sekwencja w bazie danych ma unikalny tzw. numer dostępu
· w przypadku bazy nukleotydowej (GenBank) numer ten ma postać XXnnnnnn.n, gdzie X oznacza dowolną literę, zaś n liczbę
· każda sekwencja, zarówno w bazie białkowej, jak i nukleotydowej ma przypisany globalny identyfikator (GI) – ośmiocyfrową liczbę, która jest absolutnie unikalna, nie tylko w obrębie danej bazy, ale we wszystkich innych bazach sekwencyjnych; jest również wewnętrznym identyfikatorem NCBI
· trzeci rodzaj identyfikatora to tzw. RefSeq Id; ma on format NX_nnnnnn.n, gdzie X=C dla chromosomów, X=M dla transkryptów, X=T dla sztucznych wektorów, X=P dla białek; rekordy RefSeq są danymi odniesienia
Bazy map genetycznych i fizycznych:
· bardzo duża kolekcja map zgromadzona jest w NCBI, w sekcji Genome; dostęp do tych informacji realizowany jest poprzez aplikację MapView
· NCBI zintegrowała wiele map różnych typów – genetyczne, cytogenetyczne, fizyczne, hybryd poradiacyjnych
· mapa genetyczna – odległości między markerami są podane w centymorganach (1 centymorgan = 1% rekombinacji)
· mapy genomów pozwalają na klonowanie interesującego nas odcinka genomu, co w przypadku eukariontów wymaga zlokalizowania genu na jednym z chromosomów, a następnie w jego obrębie; mapy fizyczne, w szczególności mapy klonów ze zlokalizowanymi markerami bardzo upraszczają sytuację
· mapy cytogenetyczne – tworzy się przy pomocy techniki FISH; sondy fluorescencyjne hybrydyzuje się do określonej sekwencji
· najprostszymi rodzajami map fizycznych są mapy restrykcyjne; tworzy się je trawiąc DNA genomowe różnymi kombinacjami enzymów restrykcyjnych i następnie ustalając kolejność miejsc cięcia
Bazy struktur:
· gromadzą informacje o przestrzennej budowie makromolekuł (białek i kwasów nukleinowych)
· najważniejsze bazy danych to:
- PDB (Protein Data Bank)
- MMDB (Molecular Modelling Data Base)
· dane w MMDB są dużo bardziej sformalizowaną i łatwiejszą do obróbki komputerowej wersją struktur z PDB
· w MMDB znajdują się struktury określone wyłącznie eksperymentalnie, zaś w PDB również modele teoretyczne
Bazy literatury:
· główną bazą danych literatury dla nauk biologicznych jest PubMed, prowadzony przez NCBI
· rekordy w tej bazie danych zawierają:
- tytuł publikacji
- autorów i ich afiliację
- dane o czasopiśmie, w którym ukazała się publikacja
- datę publikacji
- unikalny identyfikator PMID
- abstrakt
· bardzo wygodną cechą PubMed jest zamieszczanie linków do artykułów związanych z właśnie przeglądanym
Bazy informacji o ekspresji genów:
· istnieją geny różnie eksprymowane u ludzi chorych i zdrowych, związane ze specyficznymi jednostkami chorobowymi
WYKŁAD 2, 1/03/2012
Przeszukiwanie baz sekwencji
Przeszukiwanie baz danych sekwencji polega na skonstruowaniu alignmentu, czyli dopasowaniu sekwencji kwerendowej do sekwencji poszukiwanej. Konstrukcja alignmentu zachodzi nie w obrębie całej bazy danych, ale w obrębie rekordów, które dadzą istotne wyniki (idea algorytmu heurystycznego).
Niech A będzie alfabetem (np. A = {A, C, T, G} dla sekwencji nukleotydowej), z którego pochodzą symbole w dwóch zbiorach X i Y, o liczności odpowiednio n i m (i = 0, 1, …, n, xi należy do A; j = 0, 1, …, n, yj należy do A).
Zbiory te nazywamy sekwencjami. Alignmentem sekwencji X i Y nazywamy uporządkowany zbiór par PI (xi, yj), takich, że:
VI: iI > iI-1 ^ jI > jI-1
Chodzi o to, by zmaksymalizować liczbę kolumn o identycznych wartościach.
Rodzaje alignmentów:
1. alignmenty dzielimy na dwie klasy:
· globalne – dopasowywane są całe sekwencje, niezależnie od różnicy długości
· lokalne – dopasowywane są najlepiej pasujące fragmenty sekwencji
2. z przyczyn obliczeniowych wyróżniamy:
· alignmenty dwóch sekwencji
· alignmenty wielu sekwencji
Ocena alignmentu
Odróżnianie alignmentów „lepszych” od „gorszych” wymaga jakiejś mierzalnej wartości. Liczbę, która mówi o „dobroci” alignmentów nazywamy score – oceną. Score zależy od:
· liczby par dopasowanych (np. AA)
· liczby par niedopasowanych (np. AG)
· wartości liczbowych przypisanych różnym parom w macierzy wagowej
· liczby i długości przerw
· przyjętego sposobu liczenia kar za przerwy i ich wartości
Matematycznie, score jest sumą score wszystkich par dopasowanych i kar za przerwy.
Macierz wagowa to tablica, w której wszystkim możliwym parom symboli z danego alfabetu przypisano jakieś wartości liczbowe. Macierze wagowe mają prostą interpretację probabilistyczną – im wyższy jest score przypisany danej parze symboli, tym większe prawdopodobieństwo napotkania takiej pary w „dobrych” alignmentach i odwrotnie.
Kary za przerwy
Najczęściej stosuje się dwa rodzaje funkcji ważącej przerwy:
· liniowe: GP(g) = dg
· afiniczne: GP(g) = d + (g-1)e
W modelu afinicznym g oznacza długość przerwy, d oznacza karę za otwarcie przerwy, natomiast e karę za jej przedłużenie.
Ponieważ prawdopodobieństwo powstania przerwy o długości n nie jest na ogół równe prawdopodobieństwu powstania n przerw o długości 1 (insercje lub delecje mogą zachodzić blokami), bardziej realistyczny jest model afiniczny, który wprowadza mniejszą karę za przedłużenie już otwartej przerwy. Z tego powodu jest on szerzej stosowany niż model liniowy.
Macierze twarde (np. BLOSUM80) uzyskujemy z sekwencji, które niewiele się od siebie różnią. Te macierze dużo wyżej nagradzają idealne dopasowania. Macierze miękkie (np. BLOSUM45) łagodniej karzą przerwy lub nieidealne dopasowania.
Istnieją algorytmy umożliwiające obliczenie alignmentu optymalnego dowolnych dwóch sekwencji. Alignment globalny oblicza się zgodnie z algorytmem Needlemana-Wunscha. Alignment lokalny konstruuje się przy pomocy algorytmu Smith-Watermana. Algorytmy te stosują techniki programowania dynamicznego – podziału dużego problemu na mniejsze, łatwe do rozwiązania.
Przeszukiwanie baz sekwencji polega na:
· dopasowaniu sekwencji kwerendowej do każdej sekwencji w bazie (po kolei)
· stwierdzeniu, które dopasowania są wynikiem przypadku (losowe), a które są efektem wspólnego pochodzenia i podobieństwa struktury (statystycznie istotne)
Do konstrukcji dopasowania można wykorzystać dowolny algorytm, jednak te oparte na programowaniu dynamicznym są zbyt wolne.
...