1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2023/24
CI05
Obsah
MinHash
Motivácia: Pri zostavovaní genómov pomocou overlap-layout-consensus frameworku na nájdenie prekryvov medzi čítaniami treba vykonať lokálnych zarovnaní medzi každou dvojicou čítaní (kde
je počet čítaní), pričom každé zarovnanie trvá
(kde
je dĺžka čítaní). Prirodzeným spôsobom zníženia časových nárokov je obmedzenie zarovnávaní iba medzi "sľubnými" dvojicami čítaní. Ako však také dvojice nájsť?
Odbočka do analýzy web-stránok: Podobnosť textov
Majme množinu webových stránok (webová stránka je postupnosť slov). Chceme nájsť medzi nimi dvojice podobných. Ako môžeme definovať podobnosť dvoch textov?
Jeden zo spôsobov ako to spraviť je pozrieť sa na množstvo slov, spoločných pre jednotlivé dvojice stránok. Očakávame, že čím viac spoločných slov majú, tým sú podobnejšie. Túto mieru podobnosti formalizuje matematický pojem Jaccardovej miery podobnosti.
Nech je univerzum slov a nech
sú jeho podmnožinami (t.j. množiny slov dvoch textov). Potom Jaccardova miera podobnosti
je definovaná nasledovne:
Táto miera nadobúda hodnotu 0 iba prípade, ak množiny sú disjunktné, a hodnotu 1 iba v prípade, že množiny sú totožné. Inak sa jej hodnota nachádza na otvorenom intervale , a čím viac spoločných slov majú, tým je jej hodnota vyššia.
Potom otázku "Ktoré dvojice textov sú podobné?" môžeme preformulovať napríklad ako "Ktoré dvojice textov majú Jaccardovu mieru podobnosti vyššiu ako ?", kde
je nejaká prahová hodnota.
Exaktný výpočet Jaccardovej miery podobnosti nie je vždy dostatočne rýchly pre účely konkrétnej aplikácie, takže logickým riešením je pokúsiť sa jej hodnotu vypočítať iba približne (t.j. aproximovať).
Aproximácia Jaccardovej miery: MinHash
Nech je daná množina . Nech
je injektívna náhodná hashovacia funkcia (t.j. bez kolízií). Potom minimálny hash množiny
je definovaný nasledovne:
Keďže je náhodná hashovacia funkcia, tak sa na hodnotu
môžeme pozerať ako na náhodnú premennú, ktorá reprezentuje rovnomerne náhodný výber prvku z množiny
.
Nech je náhodná premenná, ktorá nadobúda hodnotu 1, ak
, a inak hodnotu 0. Potom
Potom
.
Z toho vyplýva, že náhodná premenná je nevychýleným odhadom Jaccardovej miery. Je to však veľmi nepohodlný odhad, lebo namiesto celej škály hodnôt od 0 po 1 vracia len dve možnosti.
V štatistike základnou mierou kvality nevychýleného odhadu slúži jeho variancia . Spočítajme si postupne obe hodnoty.
Čiže . Aká je maximálna možná hodnota variancie?
Táto otázka je ekvivalentná otázke "Aké je maximum funkcie na intervale
?". Pre určenie extrémov hladkých funkcií treba nájsť korene jej prvej derivácie. Derivácia tejto funkcie je
, jej koreň je hodnota
. Hodnota funkcie v tomto bode je rovná
. Čiže
.
Ako môžeme tento odhad zlepšiť?
Jedna z možností je zobrať viacero nezávislých hashovacích funkcií , a spočítať
pre obidve množiny. Označme si príslušné náhodné premenné ako
. Každá z nich má strednú hodnotu
a rovnakú varianciu
.
Nech náhodná premenná je ich priemer. Potom jej stredná hodnota je rovná
. Čiže aj
je nevychýleným odhadom Jaccardovej miery.
Pozrieme sa na jej varianciu:
(*) tento prechod je možný len kvôli tomu, že premenné sú nezávislé.
Vidíme teda, že varianciu (resp. kvalitu) môžeme potlačiť na ľubovoľne malú postupným zvýšením počtu hashov.
Všimnite si, že premenná (t.j. nie priemer, ale súčet jednotlivých
) je súčtom nezávislých indikátorov s rovnakou distribúciou, a teda má binomické rozdelenie s parametrami
a
.
Druhá možnosť zlepšenia je nechať jednu hashovaciu funkciu, ale porovnávať nie 1, ale k najmenších hashov dvoch množín. Vedie to ku podobnému asymptotickému správaniu.
Návrat do porovnávania sekvencií
Ako "slová" použijeme všetky súvislé podreťazce fixnej dĺžky (dĺžka sa tradične označuje ako ) danej sekvencie. Tieto podreťazce sa tradične označujú ako
-mery.
Potom na hľadanie dvoch podobných čítaní z množiny čítaní môžeme použiť minhash.
V prípade BLAST, t.j. lokálneho zarovnávania dvoch sekvencií sa ako texty berú okná (t.j. súvislé podreťazce väčšej dĺžky než ). Potom dvojice podobných okien plnia tú istú funkciu ako jadrá zarovnávania v klasickom BLASTe.
- Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018 Sep 15;34(18):3094-100. [1]
- Roberts M, Hayes W, Hunt BR, Mount SM, Yorke JA. Reducing storage requirements for biological sequence comparison. Bioinformatics. 2004 Dec 12;20(18):3363-9. [2]