Seminář z bioinformatiky
Eva Dobešová
Zarovnání sekvencí z bisulfitového sekvenování
Úloha 5meC v DNA
• DNA: A, G, T, C
• 5. báze v DNA: 5-methylcytosin
– Epigenetická modifikace ovlivňující spoustu procesů:
– Embryonální vývoj, genomový imprinting, strukturu
chromatinu, transkripci genů, umlčování transpozonů…
– Abnormální methylace byla objevena u Alzheimerovy
choroby a rakoviny.
• Jak stanovit 5meC v DNA?
Bisulfitové sekvenování
• Bisulfit: konvertuje nemethylované cytosiny na uracily
(po PCR převedeny na thyminy), 5meC zůstává
nezměněn.
• Umožňuje zachytit methylaci cytosinů na úrovni
jediného nukleotidu
• Dochází ke změně v sekvenci C-G → T-A
Hardcastle PlantMethods 2013, 9:16
SOLiD
• Princip sekvenace: • Na rozdíl od metod 454 a
Illumina využívá sekvenování
na základě ligace (ale PCR
reakce při přípravě knihovny)
• Využívá tzv. dvoubázové
kódování:
• Každá báze je čtena dvakrát,
možné rozeznání chyb od
substitucí
• Výstup: color-space reads
• Dříve: délka 35 bp a přesnost 99,85 %
• Dnes: 85 bp a 99,99%
Odkud obtížnost pramení:
• Jak zarovnat sekvence, které obsahují hodně
„mutací“?
– těžko
• Sekvenované ready mají místo některých C → T,
resp. místo G → A (na druhém vláknu)
• SOLiD – snadná detekce SNPs, ale bisulfitem
indukované nukleotidové substituce (BINS) jsou
časté a způsobují příliš mnoho nesprávných
spojení (mismatch).
Přístupy zarovnání sekvencí
• Použít 4 referenční sekvence: původní a plně
konvertovanou bisulfitem pro obě vlákna
(Watson a Crick vlákno) → zarovnat tradičními
nástroji pro SOLiD
– Problém: ready obsahují jak methylované tak
nemethylované cytosiny („napůl methylované“ se
nepřiřadí)
Přístupy zarovnání sekvencí
• Použít 4 referenční sekvence: původní a plně
konvertovanou bisulfitem pro obě vlákna
(Watson a Crick vlákno) → zarovnat tradičními
nástroji pro SOLiD
– Problém: ready obsahují jak methylované tak
nemethylované cytosiny
• Převést SOLiD ready z dvounukleotidového
kódování na řetězec nukleotidů a zarovnat
existujícími nástroji, které jsou tolerantní k
BINS (předpokládá absenci sekvenačních
chyb).
Zarovnání sekvencí vyjádřených jako
řetězec nukleotidů
• Zarovnání BS-seq dat – menší množství
informace dostupné pro zarovnání k
referenčnímu genomu oproti klasické
sekvenaci.
• 2 přístupy:
– unbiased alignment (zarovnání bez chyb-mismatchů)
– biased alignment
• Unbiased alignment (three-letter alignment):
– In silico konverze všech cytosinů na thyminy,
(sekvenované readech i referenční sekvence)
– Výsledkem jsou sekvence obsahující pouze 3 báze
(A,G,T), méně readů je přiřazeno jednoznačně
– BS-Seeker,Bismark, MethylCoder, BRAT
• Biased alignment (Wildcard alignment):
– Sekvenované thyminy jsou konvertovány na Y (C
nebo T), resp. C v genomu → Y
– Jednoznačnější přiřazení než u unbiased
alignment, využívá maximální možnou informaci
– BSMap, RMAP-BS
• Biased alignment (Wildcard alignment):
– Sekvenované thyminy jsou konvertovány na Y (C
nebo T), resp. C v genomu → Y
– Jednoznačnější přiřazení než u unbiased
alignment, využívá maximální možnou informaci
– BSMap, RMAP-BS
– Možné využít upravenou skórovací matici
a c g t
a 6 -18 -18 -18
c -18 6 -18 3
g -18 -18 6 -18
t -18 -18 -18 3
Sloupce znázorňují báze v sekvenovaných readech, řádky báze
v referenčním genomu.
Frith Nucleic Acids Research 2012, 40:13
SOCS -B
• Algoritmus na zarovnání „barevných“ sekvencí, který
dovoluje bisulfitem indukované nukleotidové
substituce i sekvenační chyby.
• Spustitelný soubor ani zdrojový kód již nejsou dostupné
• Popis algoritmu: založený na Rabin(ově)-Karp(ově) alg.
– Vytvoření hašovací tabulky (snižuje počet zarovnání)
– Ohodnocení zarovnaní porovnáním sekvenovaných readů
vyjádřených v barevném módu s „barevnou“ referenční
sekvencí (obě fáze tolerantní k BINS i sekv. chybám)
• Hashe jsou vypočítány na základě překladu „barevných“ readů do
nukleotidové sekvence. Počítají se všechny 4 překlady.
– Klíče upraveny tak, že berou C a T jako stejný symbol.
• Pro výpočet nejpravděpodobnějšího stavu každého mC
využívá dynamické programování
Citace Scopus: 1x2011, 5x2012, 6x2013, ?2014
Rabinův-Karpův algoritmus (1987)
• Algoritmus pro vyhledávání v textu, využívající
hashovací funkce.
Wikipedia – Rabinův-Karpův algoritmus
Předpokládáme, že všechny podřetězce mají pevnou délku m
Příklad dynamické programovací
tabulky (SOCS-B)
Tmavá písmena označují povolené stavy. První nukleotid musí
odpovídat sekvenci adaptoru. Posun po zelených šipkách
neovlivňuje skóre, červené šipky odpovídají sekvenačním
chybám (3. a 4. nukleotid = CT, TC, TT – 1 sekvenační chyba).
Pozice chyby je určena tam, kde měla barva nejnižší kvalitu.
● ● ● ●
● ● ●
AT
CG
GC
TA
AG
CT
GA
TC
AC
CA
GT
TG
AC
CA
GT
TG
AT
CG
GC
TA
AT
CG
GC
TA
AT
CG
GC
TA
● ● ● ● ● ● ●
Testování algoritmu
• Analyzováno bylo 54 705 478 readů z genomu
A. thaliana (bisulf.)
• Kontrola: nástroj pro zarovnání poskytovaný
Applied Biosystems (mapreads), referenční
sekvence: plně konvertovaná Watson a Crick
vlákna a nekonvertované Watson vlákno.
• SOCS-B: reference pouze nekonvertovaný genom.
• Algoritmus byl 2x citlivější u readů obsahujících 3
a méně chyb
Technické parametry
• Doba běhu 30 h (Apple Mac Pro, dual 2.93 GHz QuadCore
Intel Xeon with hyper-threading, 32GB RAM)
• Více readů může být namapováno, pokud je
povoleno více mismatch-ů, cena: delší doba
výpočtu, nižší specificita.
• Možné distribuované zpracování.
Bock Nature Reviews Genetics 2012, 13
Praktický příklad: BiQ Analyzer HT
• Místně specifická analýza DNA methylace
• Wildcard aligner
• Vhodný pro zpracování dat z 454 sekvencí
• Zarovnávací algoritmus: Needleman-Wunsch
(lokální zarovnání)
• Program založený na jazyku Java – možné
spuštění na jakémkoli počítači
• Příjemné grafické rozhraní pro „biology“,
možná volba parametrů a filtrování dat
Lutsik Nucleic Acids Research, 2011, 1–6