Autoindex nad DNA sekvencemi

Autoindex nad DNA sekvencemi doc. Ing. Jan Holub, Ph.D. katedra teoreticke´ informatiky Fakulta informaˇcn´ıch technologi´ı ˇ Cesk e´ vysoke´ uˇcen´ı technicke´ v Praze ENBIK 2014 10. 6. 2014

ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 1/27

Obsah Úvod do problematiky Stringologie BIO-FMI Kompaktní sufixový strom pro variace ˇ Záver


Úvod do problematiky Stringologie ˇ ˇ u˚ a posloupností symbolu˚ veda o zpracování ˇretezc použití: vyhledávání dokumentu, ˚ kontrola pravopisu,. . . Komprese dat ˇ veda o úsporném ukládání dat použití: ukládání dokumentu, ˚ pˇrenos dokumentu,. ˚ ..


Biologie – úlohy Bioinformatika – úlohy uložení genomu˚ velmi aktuální nedostateˇcné kapacity disku˚ uvažuje se o zahazování dat nalezení genu˚ v genomu porovnávání genomu˚ ...


Propojení oboru˚ Stringologie

Komprese dat

pˇresn´ e vyhled´ av´ an´ı

statistick´ e metody

pˇribliˇ zn´ e vyhled´ av´ an´ı

slovn´ıkov´ e metody

indexov´ an´ı

kontextov´ e metody

neurˇ cit´ e ˇretˇ ezce

komprese pˇrirozen´ eho jazyka

Biologie sekvenace genomu

Bioinformatika sestaven´ı genomu ukl´ ad´ an´ı genom˚ u vyhled´ av´ an´ı v genomech fylogenetick´ a anal´ yza


Stringologie Pˇresné vyhledávání vzorek p = p[1..m] délky m, p ∈ Σ∗ text t = t[1..n] délky n, t ∈ Σ∗ nalezení výskytu vzorku p v textu t p = caaca t = acaccaaacaacaaca caaca caaca


Stringologie – prˇ esné vyhledávání ˇ Deterministický konecný automat [AHU74] a, g, t

c

c c

0

c g, t

1 g, t

a

c

a

2

3

c

4

a

a, g, t g, t a, g, t

p = caaca, Σ = {a, c, g, t}

ˇ pamet’ová složitost: O(|Q||Σ|) cˇ asová složitost: O(n) ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 7/27

5

Stringologie – prˇ esné vyhledávání ˇ Sousmerné metody Deterministický koneˇcný automat [AHU74] ˇ O(|Q||Σ|); cˇ as: O(n) pamet’: Knuth-Morris-Pratt [KMP77] ˇ O(|Q|); cˇ as: O(n) pamet’: ˇ Protismerné metody Boyer-Moore [BM77] ˇ O(|Q|); cˇ as: prum ˇ ∼ (n/m), O(nm) pamet’: ˚ er rodina Boyer-Mooreových algoritmu˚ [Horspool 1980], [Sunday 1990], . . .


Stringologie – úplný index Úplný index pˇredzpracování textu t = t[1..n] vyhledání výskytu˚ vzorku p = p[1..m] v cˇ ase O(m), cˇ ili nezávisle na délce textu t Sufixový strom

c

a

a a

c a c a a

c

a

t = caaca ˇ pˇrijímá všechny pˇrípony t a rozpozná všechny podˇretezce t ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 9/27

Stringologie – úplný index sufixov´ y strom c

a

a a

c a c

minimalizace

zhutnˇen´ı a a

c

a

kompaktn´ı sufixov´ y strom

sufixov´ y automat

aca a a c

a

a

c c

a

ca

a ca aca

kompaktn´ı sufixov´ y automat zhutnˇen´ı a ca

ca, aca

minimalizace

aca


Stringologie – úplný index Implementace: sufixový automat implementace: [Balík, 2003] ˇ zlepšení 21–30n → 1,6–3,66n pamet’: kompaktní sufixový automat implementace: [Holub, Crochemore, 2003] ˇ zlepšení 10–15n → 1,5–3,02n pamet’:


Stringologie – úplný index Základní charakteristiky indexovacích struktur cˇ as vyhledání sufixový strom O(m) kompaktní sufixový strom O(m) sufixový automat O(m) kompaktní sufixový automat O(m) sufixové pole O(m + log n)

cˇ as konstrukce max. velikost O(n2 ) n2 O(n log |Σ|) 2n O(n log |Σ|) 2n − 1 O(n log |Σ|) n+1 O(n2 log n) n

maximální velikost = maximální poˇcet stavu˚ automatu nebo maximální velikost sufixového pole


Stringologie – autoindex ˇ index zhuštený ˇ index co do velikosti úmerný délce textu t (do délky 2n) autoindex ˇ index schopný nahradit puvodní zhuštený ˚ text t ˇ ˇ (umožnuje efektivneˇ zobrazit libovolný podˇretezec t)


Biologie – ukládání genomu˚ vstup: r genomu˚ jednoho druhu: t0 , t1 , . . . , tr−1 genomy dvou lidí se liší v 0,1 % úkol: efektivneˇ uložit, umožnit vyhledávání ˇrešení: Klasické metody nejsou efektivní. BIO-FMI [Procházka, Holub, 2014] ˇ kompaktní sufixový strom (KSS) zobecnený ˇ zˇretezíme genomy za sebe a vytvoˇríme KSS KSS pro variace [Holub a kol., 2013] ˇ ˇ vytvoˇríme vytvoˇríme ˇretezec s variacemi a pro nej KSS ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 14/27

BIO-FMI t0 referenˇcní genom, |t0 | = n ti = Ri,0 Ci,0 Ri,1 . . . Ci,ki −1 Ri,ki , 0 < i ≤ r

ˇ Ci,j (0 ≤ j < ki ) je shodný segment, t.j. podˇretezec ti odpovídající segmentu v t0 ˇ Ri,j (0 ≤ j ≤ ki ) odlišný segment, t.j. podˇretezec ti následující shodný segment Ci,j−1


BIO-FMI BIO-FMI – vlnkový strom + FM-index optimalizovaný pro množinu podobných DNA sekvencí

ˇ vs. cˇ as vyhledání): parametr lc (kompresní pomer maximální délka cˇ ásti vzorku ˇ Vzorek p[1, m] je rozdelen na cˇ ásti p[1, m] = p[1, lc ]p[lc + 1, 2lc ] . . . p[⌊ m lc ⌋lc , m] a jednotlivé ˇ cˇ ásti jsou vyhledány separátne.


BIO-FMI a) T0

ACCTGTAAC

T0

ACC– – –AAC

Ti

Ri,j

Ci,j

ACC– – – AAC

Ci,j−1

Ti

ACCTCTAAC

(DEL, p, 3, q − p)

Ti

Ri,j

q lc = 3

lc = 3

d

Ci,j

ACCTGTAAC

q

lc = 3

# C C A A # ...

p Ci,j−1

Ci,j

Ri,j

ACCTGTAAC

q

d

T0

p

p Ci,j−1

c)

b)

#CCTGTAA# (INS , p, 3, q − p)

d ... # C T G T A # ... (UPD, p, 1, q − p)

ˇ ti a jejich uložení v ˇretezci ˇ zmeny d i s jejich kontextem: a) smazání (DEL), b) vložení (INS), c) modifikace – jedno- nukleotidový polymorfismus (UPD).


BIO-FMI vlnkov´ y strom t0

$ a ...a

t

100110101001

1110

isLoc 0 0 0 0 1 0 ... loc

110110

000110

BW T (t0 )

c

0 $

g

a

FM-index I0 postavený pro referenˇcní sekvenci t0


t

BIO-FMI t0

...

a

sampleStart

...

vlnkov´ y strom ti

...

c

$ # ... #

...

t

100110101001

2 × lc − 1

d

# ... c

...

# +

isLoc 0 0 0 0 1 0 ...

1110

101

a

0 $

loc

aIndex

010110

000110

BW T (d )

#

c

t g

+

aBasePos aOffset aOp

ˇ ˇ d FM-index Id postavený pro ˇretezec zmen


BIO-FMI lc

lc

}|

z

{z

}|

lc

{z

}|

lc

{z

}|

{

p p1

p2

p3

v´ yskyty:

p1

v´ yskyty:

p2

p4

t0 :

i101 , i102 , i103 , i104 , . . .

t1 :

i111 , i112 , i113 , . . .

t2 : .. .

i121 , i122 , i123 , . . .

t0 :

i201 , i202 , i203 , i204 , . . .

t1 :

i211 , i212 , i213 , . . .

t2 : .. .

i221 , i222 , i223 , . . .

.. skládání výskytu vzorku p z výskytu˚ jeho cˇ ástí p1 , p2 , . . . ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 20/27

BIO-FMI – Experimenty File

s001

s005

m

5

10

lc

5

5

10

10

2.26 %

2.26 %

2.99 %

2.56 µs

993.88 µs

3.80 µs

BIO-FMI

RLCSA

LZ77

LZ-End

20

5

10

20

20

5

5

10

10

20

2.99 %

5.08 %

6.01 %

6.01 %

8.69 %

8.69 %

14.15 %

28.97 µs

25.77 µs

2.37 µs

956.41 µs

3.71 µs

30.83 µs

25.94 µs

6.38 %

6.38 %

6.38 %

9.32 %

9.32 %

9.32 %

13.83 µs

12.71 µs

18.26 µs

19.83 µs

22.78 µs

23.80 µs

3.47 %

3.47 %

3.47 %

8.18 %

8.18 %

8.18 %

133.96 µs

156.16 µs

164.95 µs

82.10 µs

122.85 µs

166.67 µs

6.19 %

6.19 %

6.19 %

16.01 %

16.01 %

16.01 %

33.60 µs

44.41 µs

154.64 µs

44.00 µs

83.22 µs

156.25 µs

ˇ a cˇ asy nalezení pro soubory s001 a s005 (pravdepodobnost ˇ ˇ Kompresní pomer zmeny mezi ti a t0 je 0, 1 % respektive 0, 5 %). R Intel CoreTM 2 Duo CPU T6600 2.20 GHz, 4 GB RAM

další autoindexy: RLCSA [Mäkinen, Navarro, Sirén, Välimäki, 2010], LZ77 self-index [Kreft, Navarro, 2011] and LZ-End self-index [Kreft, 2011] ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 21/27

Kompaktní sufixový strom pro variace vstup: t0 = aaabaaabbaaba# t1 = aaabaabaabbaba$ ˇretezec ˇ s variacemi: t0+1 = aaabaa(abba/baabb)aba#

ˇ sestrojíme kompaktní sufixový strom pro ˇretezec s variacemi t0+1


Kompaktní sufixový strom pro variace

t0+1 = aaabaa(abba/baabb)aba# cˇ as vyhledání: O(m + occ(p)), kde occ(p) = poˇcet výskytu˚ ˇ O(n + ld + l1 ), kde ld je souˇcet délek odlišných pamet’: ˇ segmentu˚ a l1 je souˇcet nekterých spoleˇcných segmentu˚ ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 23/27

Stringologie – prˇ ibližné vyhledávání ˇ Výskyty vzorku p v textu t mohou obsahovat nejakou chybu. ˇ u˚ u, v ∈ Σ∗ = minimální poˇcet Vzdálenost dvou ˇretezc editaˇcních operací, které jsou zapotˇrebí pro pˇrevedení ˇretezce ˇ ˇ u na ˇretezec v Hammingova vzdálenost: substituce Levenshteinova vzdálenost: substituce, vložení a ˇ odstranení Damerauova vzdálenost: substituce, vložení, ˇ a transpozice odstranení ˇ vzdálenost indel: vložení a odstranení


Stringologie – neurcˇ ité rˇ eteˇ zce neurˇcitý symbol zastupuje více než jeden symbol základní abecedy. rozšíˇrení don’t care symbolu pˇríklad: základní abeceda Σ = {a, c, g, t} rozšíˇrená abeceda Σ′ = 2Σ \ {∅} H = {a, c, t} ˇ neurˇcitý rˇetezec ˇretezec ˇ obsahující neurˇcité symboly aminokyselina isoleucin atH


Biologie – neurcˇ ité rˇ eteˇ zce Protein kódován aminokyselinami aminokyselina kódovaná trojicí nukledotidu˚ 20 aminokyselin T C A G T TTT fenylalanin TCT serin TAT tyrosin TGT cystein TTC fenylalanin TCC serin TAC tyrosin TGC cystein TTA leucin TCA serin TAA stop TGA stop TTG leucin TCG serin TAG stop TGG tryptofan C CTT leucin CCT prolin CAT histidin CGT arginin CTC leucin CCC prolin CAC histidin CGC arginin CTA leucin CCA prolin CAA glutamin CGA arginin CTG leucin CCG prolin CAG glutamin CGG arginin A ATT isoleucin ACT treonin AAT asparagin AGT serin ATC isoleucin ACC treonin AAC asparagin AGC serin ATA isoleucin ACA treonin AAA lysin AGA arginin ATG metionin ACG treonin AAG lysin AGG arginin G GTT valin GCT alanin GAT kys. asparagová GGT glycin GTC valin GCC alanin GAC kys. asparagová GGC glycin GTA valin GCA alanin GAA kys. glutamová GGA glycin GTG valin GCG alanin GAG kys. glutamová GGG glycin ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 26/27

Záveˇ r a výhled do budoucna Výsledky: BIO-FMI: ˇ až 2,26 %, velmi rychlé kompresní pomer vyhledávání, s rostoucí délkou vzorku efektivita klesá KSS: rychlost vyhledávání neklesá s rostoucí délkou vzorku, zatím není praktická implementace Výhled do budoucna: ˇ u˚ a pˇribližného prozkoumat možnosti neurˇcitých ˇretezc vyhledávání praktické nasazení v používaných systémech ENBIK 2014, 10. 5. 2014 – J. Holub: Autoindex nad DNA sekvencemi – p. 27/27

Autoindex nad DNA sekvencemi

Recommend Documents