Sekvenční analýza bez zarovnání - Alignment-free sequence analysis

v bioinformatika, sekvenční analýza bez zarovnání přístupy k údajům o molekulární sekvenci a struktuře poskytují alternativy k přístupům založeným na vyrovnání.^[1]

Vznik a potřeba analýzy různých typů údajů generovaných biologickým výzkumem vedly k rozvoji oblasti bioinformatika.^[2] Molekulární sekvence a strukturní data DNA, RNA, a bílkoviny, genová exprese profily nebo microarray data, metabolická cesta data jsou některé z hlavních typů dat analyzovaných v bioinformatice. Mezi nimi sekvenční data rostou exponenciálním tempem v důsledku nástupu sekvenčních technologií nové generace. Od vzniku bioinformatiky sekvenční analýza zůstala hlavní oblastí výzkumu s širokou škálou aplikací při prohledávání databáze, anotace genomu, komparativní genomika, molekulární fylogeneze a genová předpověď. Průkopnické přístupy pro sekvenční analýzu byly založeny na zarovnání sekvence globální nebo místní, párové nebo vícenásobné zarovnání sekvence.^[3][4] Přístupy založené na zarovnání obecně poskytují vynikající výsledky, když sledované sekvence úzce souvisí a lze je spolehlivě srovnat, ale když se sekvence liší, nelze dosáhnout spolehlivého zarovnání, a proto jsou aplikace sekvenčního zarovnání omezené. Dalším omezením přístupů založených na zarovnání je jejich výpočetní složitost a jsou časově náročné, a proto jsou omezené při práci s velkými daty sekvence.^[5] Příchod sekvenování nové generace technologie vyústila v generování objemných sekvenčních dat. Velikost těchto sekvenčních dat představuje výzvu pro algoritmy založené na zarovnání v jejich sestavení, anotaci a srovnávacích studiích.

Metody bez zarovnání

Metody bez zarovnání lze obecně rozdělit do pěti kategorií: a) metody založené na k-mer / frekvence slov, b) metody založené na délce běžných podřetězců, c) metody založené na počtu (rozmístěných) slovních shod, d) metody založené na mikro-zarovnání, e) metody založené na teorii informací af) metody založené na grafickém znázornění. Při vyhledávání podobnosti sekvence byly použity přístupy bez zarovnání,^[6] shlukování a klasifikace sekvencí,^[7] a v poslední době ve fylogenetice^[8][9] (Obrázek 1).

Říká se, že takové analýzy molekulární fylogeneze využívající přístupy bez zarovnání jsou součástí fylogenomika nové generace.^[9] Řada recenzních článků poskytuje hloubkový přehled metod bez zarovnání v sekvenční analýze.^{[1][10][11][12][13][14][15]}

The AFproject je mezinárodní spolupráce pro srovnávání a porovnávání softwarových nástrojů pro srovnání sekvencí bez zarovnání.^[16]

Metody založené na k-mer / frekvence slov

Populární metody založené na k- kmitočty slov / slov zahrnují frekvenční profil funkce (FFP),^[17][18] Kompoziční vektor (CV),^[19][20] Distribuce doby návratu (RTD),^[21] reprezentace hry s frekvenčním chaosem (FCGR).^[22] a rozložená slova^[23]

Profil frekvencí prvků (FFP)

Metodika použitá v metodě založené na FFP začíná výpočtem počtu všech možných k-mer (možný počet k-mer pro nukleotidovou sekvenci: 4^k, zatímco pro proteinovou sekvenci: 20^k) v sekvencích. Každý k-mer počet v každé sekvenci se pak normalizuje vydělením celkem celkem kpočet počítajících v tomto pořadí. To vede k převodu každé sekvence do jejího frekvenčního profilu funkce. Poté se vypočítá párová vzdálenost mezi dvěma sekvencemi Jensen – Shannon (JS) divergence mezi jejich příslušnými FFP. The matice vzdálenosti takto získané lze použít ke konstrukci fylogenetický strom pomocí shlukových algoritmů jako sousedství, UPGMA atd.

Složení vektor (CV)

V této metodě frekvence výskytu každého možného k-mer v dané sekvenci se vypočítá. Dalším charakteristickým krokem této metody je odčítání náhodného pozadí těchto frekvencí pomocí Markovův model snížit vliv náhodného neutrálu mutace zdůraznit roli selektivní evoluce. Normalizované frekvence jsou dány pevným řádem pro vytvoření kompozičního vektoru (CV) dané sekvence. Kosinová vzdálenost Funkce se poté používá k výpočtu párové vzdálenosti mezi CV sekvencí. Takto získanou matici vzdálenosti lze použít ke konstrukci fylogenetického stromu pomocí shlukových algoritmů, jako je sousedství, UPGMA atd. Tuto metodu lze rozšířit prostřednictvím uchýlení se k efektivním algoritmům porovnávání vzorů, které budou zahrnuty do výpočtu vektorů složení: (i) všechny k- výrobci pro jakoukoli hodnotu k, (ii) všechny podřetězce libovolné délky až do libovolně stanoveného maxima k hodnota, (iii) všechny maximální podřetězce, přičemž podřetězec je maximální, pokud by jeho prodloužení o libovolný znak způsobilo snížení počtu výskytů.^[24][25]

Distribuce doby návratu (RTD)

Metoda založená na RTD nepočítá počet k-mers v sekvencích, místo toho počítá čas potřebný pro znovuobjevení k-merové. Čas se vztahuje k počtu zbytků v postupném vzhledu konkrétního k-mer. Tedy výskyt každého z nich k-mer v sekvenci se vypočítá ve formě RTD, který se poté shrne pomocí dvou statistických parametrů znamenat (μ) a standardní odchylka (σ). Každá sekvence je tedy reprezentována ve formě numerického vektoru o velikosti 2,4^k obsahující μ a σ ze 4^k RTD. Vzdálenost mezi sekvencemi se vypočítá pomocí Euklidovská vzdálenost opatření. Takto získanou matici vzdálenosti lze použít ke konstrukci fylogenetického stromu pomocí shlukových algoritmů, jako je sousedství, UPGMA atd.

Reprezentace hry Frequency chaos (FCGR)

Metody FCGR se vyvinuly z techniky reprezentace chaosové hry (CGR), která poskytuje měřítko nezávislé reprezentace genomových sekvencí.^[26] CGR lze rozdělit mřížkovými čarami, kde každý čtverec mřížky označuje výskyt oligonukleotidů specifické délky v sekvenci. Taková reprezentace CGR se označuje jako Frequency Chaos Game Representation (FCGR). To vede k reprezentaci každé sekvence do FCGR. Párovou vzdálenost mezi FCGR sekvencí lze vypočítat pomocí Pearsonovy vzdálenosti, Hammingovy vzdálenosti nebo euklidovské vzdálenosti.^[27]

Frekvence mezer

Zatímco většina algoritmů bez zarovnání porovnává slovní složení sekvencí, Spaced Words používá vzorec péče a nezajímá pozice. Výskyt mezerového slova v sekvenci je pak definován pouze znaky na pozicích shody, zatímco znaky na pozicích nezajímají se ignorovány. Namísto porovnání frekvencí souvislých slov ve vstupních sekvencích tento přístup porovnává frekvence oddělených slov podle předem definovaného vzoru.^[23] Předdefinovaný vzor lze vybrat analýzou Rozptyl počtu zápasů,^[28] pravděpodobnost prvního výskytu na několika modelech,^[29] nebo Pearsonův korelační koeficient mezi očekávanou frekvencí slov a skutečnou vzdáleností zarovnání.^[30]

Metody založené na délce běžných podřetězců

Metody v této kategorii využívají podobnost a rozdíly podřetězců ve dvojici sekvencí. Tyto algoritmy se většinou používaly pro zpracování řetězců v počítačová věda.^[31]

Průměrný společný podřetězec (ACS)

V tomto přístupu pro vybraný pár sekvencí (A a B délek n a m ) nejdelší podřetězec začínající na nějaké pozici je identifikován v jedné sekvenci (A), která přesně odpovídá druhé sekvenci (B) na jakékoli pozici. Tímto způsobem se vypočítají délky nejdelších podřetězců začínajících na různých pozicích v sekvenci A a majících přesné shody na některých pozicích v sekvenci B. Všechny tyto délky jsou zprůměrovány k odvození míry ${ displaystyle L (A, B)}$. Intuitivně větší ${ displaystyle L (A, B)}$, čím více jsou si obě sekvence podobné. Abychom zohlednili rozdíly v délce sekvencí, ${ displaystyle L (A, B)}$ je normalizováno [tj. ${ displaystyle L (A, B) / log (m)}$]. To dává míru podobnosti mezi sekvencemi.

Aby bylo možné odvodit míru vzdálenosti, inverzní z opatření podobnosti je vzat a opravný termín je od ní odečteno, aby to bylo zajištěno ${ displaystyle d (A, A)}$ bude nula. Tím pádem

${ displaystyle d (A, B) = left [{ frac { log m} {L (A, B)}} right] - left [{ frac { log n} {L (A, Správně].}$

Toto opatření ${ displaystyle d (A, B)}$ není symetrický, takže je třeba počítat ${ displaystyle d_ {s} (A, B) = d_ {s} (B, A) = (d (A, B) + d (B, A)) / 2}$, který dává konečné ACS míry mezi dvěma řetězci (A a B).^[32] Vyhledávání subsekvencí / podřetězců lze efektivně provést pomocí stromy přípon.^[33][34][35]

k-mismatch average common substring approach (kmacs)

Tento přístup je zevšeobecněním přístupu ACS. Chcete-li definovat vzdálenost mezi dvěma sekvencemi DNA nebo proteinu, kmacs odhaduje pro každou pozici i první sekvence nejdelší podřetězec začínající na i a porovnání podřetězce druhé sekvence s až k neshody. Definuje průměr těchto hodnot jako měřítko podobnosti mezi sekvencemi a proměňuje je v symetrickou míru vzdálenosti. Kmacs nepočítá přesně k- nesoulad podřetězců, protože by to bylo výpočetně příliš nákladné, ale přibližuje se takovým podřetězcům.^[36]

Mutační vzdálenosti (Kr)

Tento přístup úzce souvisí s ACS, který vypočítává počet substitucí na místo mezi dvěma sekvencemi DNA pomocí nejkratšího chybějícího podřetězce (označovaného jako shustring).^[37]

Distribuce délky běžných podřetězců k-nesouladu

Tento přístup využívá program kmacs^[36] pro výpočet nejdelších běžných podřetězců s až k nesoulady pro pár sekvencí DNA. Fylogenetickou vzdálenost mezi sekvencemi lze poté odhadnout z lokálního maxima v distribuci délky společných podřetězců k-neshody.^[38]

Metody založené na počtu (rozmístěných) shod slov

${ displaystyle D_ {2} ^ {S}}$ a ${ displaystyle D_ {2} ^ {*}}$

Jedná se o varianty ${ displaystyle D_ {2}}$ statistika, která počítá počet ${ displaystyle k}$-mer shody mezi dvěma sekvencemi. Vylepšují jednoduchost ${ displaystyle D_ {2}}$ statistiky tím, že vezmeme v úvahu distribuci pozadí porovnávaných sekvencí.^[39]

KAŠE

Jedná se o extrémně rychlou metodu, která k odhadu využívá strategii skici MinHash dole Jaccardův index z více sad ${ displaystyle k}$-majitelé dvou vstupních sekvencí. To znamená, že odhaduje poměr ${ displaystyle k}$-mer odpovídá celkovému počtu ${ displaystyle k}$- tvůrci sekvencí. To lze zase použít k odhadu evolučních vzdáleností mezi porovnávanými sekvencemi, měřeno jako počet substitucí na pozici sekvence, protože sekvence se vyvinuly z jejich posledního společného předka.^[40]

Sklon stromu

Tento přístup vypočítává hodnotu vzdálenosti mezi dvěma proteinovými sekvencemi na základě rozpadu počtu ${ displaystyle k}$-mer odpovídá, pokud ${ displaystyle k}$ zvyšuje.^[41]

Slope-Spa M.

Tato metoda vypočítá počet ${ displaystyle N_ {k}}$ z ${ displaystyle k}$-mer nebo shoda s mezerami (SpaM) pro různé hodnoty délky slova nebo počtu pozic shody ${ displaystyle k}$ v podkladovém vzoru. Sklon afinně-lineární funkce ${ displaystyle F}$ to záleží na ${ displaystyle N_ {k}}$ se vypočítá pro odhad vzdálenosti Jukes-Cantor mezi vstupními sekvencemi.^[42]

Skmer

Skmer vypočítá vzdálenosti mezi druhy z nesestavených sekvenčních čtení. Podobný KAŠE, používá Jaccardův index na souborech ${ displaystyle k}$-mers ze vstupních sekvencí. Na rozdíl od KAŠE, program je stále přesný pro nízké pokrytí sekvenování, takže jej lze použít pro sklizeň genomu.^[43]

Metody založené na mikro-zarovnání

Přesně řečeno, tyto metody nejsou bez zarovnání. Používají jednoduché mezery mikro-zarovnání kde se sekvence musí shodovat na určitých předem definovaných pozicích. Pozice zarovnané na zbývajících pozicích mikro-zarovnání tam, kde jsou povoleny neshody, se pak použijí pro odvození fylogeneze.

Co-fylog

Tato metoda hledá tzv struktur které jsou definovány jako páry k-mer shody mezi dvěma sekvencemi DNA, které jsou v obou sekvencích od sebe vzdálené. Dva k-mer zápasy se nazývají kontext, pozice mezi nimi se nazývá objekt. Co-phylog pak definuje vzdálenost mezi dvěma sekvencemi, zlomek takové struktur pro které jsou dva nukleotidy v objekt jsou rozdílní. Tento přístup lze použít u nesestavených sekvenčních čtení.^[44]

andi

andi odhaduje fylogenetické vzdálenosti mezi genomovými sekvencemi na základě neuzavřeného místního zarovnání, které je ohraničeno maximálními přesnými shodami slov. Takové shody slov lze efektivně najít pomocí polí přípon. Zarovnání bez mezer mezi přesnými shodami slov se poté použije k odhadu fylogenetických vzdáleností mezi sekvencemi genomu. Výsledné odhady vzdálenosti jsou přesné až pro přibližně 0,6 substitucí na pozici.^[45]

Filtrované shody mezerami (FSWM)

FSWM používá předdefinovaný binární vzor P představující tzv pozice v zápase a nezajímají pozice. Pro pár vstupních sekvencí DNA pak hledá shody s mezerami w.r.t. P, tj. pro lokální srovnání bez mezer s odpovídajícími nukleotidy na pozice v zápase z P a možné neshody na webu nezajímají pozice. Rušivé shody s mezerami s nízkým bodovým hodnocením jsou zahozeny, evoluční vzdálenosti mezi vstupními sekvencemi jsou odhadovány na základě vzájemně seřazených nukleotidů na nezajímají pozice zbývajících homologních shod s mezerami.^[46] FSWM byl upraven tak, aby odhadoval vzdálenosti na základě nesestavených čtení NGS, tato verze programu se nazývá Read-Spa M..^[47]

Prot-Spa M.

Prot-SpaM (Protna bázi eome Lázněced-word Matches) je implementace algoritmu FSWM pro částečné nebo celé sekvence proteomu.^[48]

Multi-Spa M.

Multi-SpaM (MultipleLázněced-word Matches) je přístup k rekonstrukci fylogeneze založené na genomu, který rozšiřuje myšlenku FSWM na srovnání více sekvencí.^[49] Vzhledem k binárnímu vzoru P z pozice v zápase a nezajímají poziceprogram hledá P-bloky, tj. lokální čtyřcestné zarovnání bez mezer s odpovídajícími nukleotidy na pozice v zápase z P a možné neshody na webu nezajímají pozice. Taková čtyřcestná uspořádání jsou náhodně vzorkována ze sady vstupních sekvencí genomu. Pro každého P-block, nekořenná stromová topologie se vypočítá pomocí RAxML.^[50] Program Kvarteto MaxCut se potom použije k výpočtu superstromu z těchto stromů.

Metody založené na teorii informací

Teorie informací poskytla úspěšné metody pro analýzu a srovnání sekvencí bez seřazení. Stávající aplikace teorie informací zahrnují globální a lokální charakterizaci DNA, RNA a proteinů, odhad entropie genomu na klasifikaci motivu a oblasti. Také to slibuje genové mapování, sekvenování nové generace analýza a metagenomika.^[51]

Korelace základna-základna (BBC)

Base-base correlation (BBC) převádí sekvenci genomu na jedinečný 16rozměrný numerický vektor pomocí následující rovnice,

${ displaystyle T_ {ij} (K) = součet _ { ell = 1} ^ {K} P_ {ij} ( ell) cdot log _ {2} left ({ frac {P_ {ij } ( ell)} {P_ {i} P_ {j}}} vpravo)}$

The ${ displaystyle P_ {i}}$ a ${ displaystyle P_ {j}}$ označuje pravděpodobnosti základen i a j v genomu. The ${ displaystyle P_ {ij} ( ell)}$ označuje pravděpodobnost bází i a j na dálku ℓ v genomu. Parametr K. označuje maximální vzdálenost mezi základnami i a j. Rozdíly v hodnotách 16 parametrů odrážejí odchylky v obsahu a délce genomu.^[52][53][54]

Informační korelace a korelace částečných informací (IC-PIC)

IC-PIC (korelace informací a parciální korelace informací) metoda založená na bázi základní korelace sekvence DNA. IC a PIC byly vypočítány pomocí následujících vzorců,

${ displaystyle IC _ { ell} = - 2 sum _ {i} P_ {i} log _ {2} P_ {i} + sum _ {ij} P_ {ij} ( ell) log _ { 2} P_ {ij} ( ell)}$

${ displaystyle PIC_ {ij} ( ell) = (P_ {ij} ( ell) -P_ {i} P_ {j} ( ell)) ^ {2}}$

Konečný vektor se získá takto:

${ displaystyle V = {IC _ { ell} přes PIC_ {ij} ( ell)} { text {kde}} ell in left { ell _ {0}, ell _ {0} +1, ldots, ell _ {0} + n right },}$

který definuje rozsah vzdálenosti mezi základnami.^[55]

Párová vzdálenost mezi sekvencemi se vypočítá pomocí Euklidovská vzdálenost opatření. Takto získanou matici vzdálenosti lze použít ke konstrukci fylogenetického stromu pomocí shlukových algoritmů, jako je sousedství, UPGMA, atd..

Komprese

Příklady jsou efektivní aproximace Kolmogorovova složitost, například Složitost Lempel-Ziv. Obecně metody založené na kompresi používají vzájemné informace mezi sekvencemi. To je vyjádřeno podmíněně Kolmogorovova složitost, tj. délka nejkratšího samooddělovacího programu požadovaného ke generování řetězce vzhledem k předchozí znalosti druhého řetězce. Toto opatření má vztah k měření k- slova v sekvenci, protože je lze snadno použít ke generování sekvence. Je to někdy výpočetně náročná metoda. Teoretický základ pro Kolmogorovova složitost přístup položili Bennett, Gacs, Li, Vitanyi a Zurek (1998) návrhem informační vzdálenost.^[56] The Kolmogorovova složitost je nepočitatelný, byl aproximován kompresními algoritmy. Čím lépe komprimují, tím lépe jsou. Li, Badger, Chen, Kwong, Kearney a Zhang (2001) použili neoptimální, ale normalizovanou formu tohoto přístupu,^[57] a optimální normalizovaná forma Li, Chen, Li, Ma a Vitanyi (2003) se objevila v ^[58] a podrobněji a prokázali to Cilibrasi a Vitanyi (2005) v.^[59]Otu a Sayood (2003) použili Složitost Lempel-Ziv metoda pro konstrukci pěti různých měr vzdálenosti pro fylogenetický strom konstrukce.^[60]

Komprese kontextového modelování

V komplexitě kontextového modelování jsou predikce dalšího symbolu jednoho nebo více statistických modelů kombinovány nebo soutěží o predikci založenou na událostech zaznamenaných v minulosti. Algoritmický informační obsah odvozený z každé predikce symbolu lze použít k výpočtu algoritmických informačních profilů s časem úměrným délce sekvence. Tento proces byl aplikován na sekvenční analýzu DNA.^[61]

Metody založené na grafickém znázornění

Iterované mapy

Použití iterovaných map pro sekvenční analýzu poprvé představil HJ Jefferey v roce 1990^[26] když navrhoval použít Hra chaosu mapovat genomové sekvence do jednotkového čtverce. Tato zpráva zavedla postup jako Chaos Game Representation (CGR). Avšak pouze o 3 roky později byl tento přístup poprvé odmítnut jako projekce markovské přechodové tabulky N Goldmanem.^[62] Tato námitka byla zrušena na konci tohoto desetiletí, kdy bylo zjištěno opak - že CGR bijektivně mapuje Markovův přechod do fraktální reprezentace bez řádů (bez stupňů).^[63] Uvědomění si, že iterované mapy poskytují bijektivní mapu mezi symbolickým prostorem a číselným prostorem, vedlo k identifikaci různých přístupů k porovnání sekvencí a charakterizaci bez zarovnání. Tento vývoj na konci roku 2013 přezkoumala společnost JS Almeida v roce 2006.^[64] Řada webových aplikací, jako je https://usm.github.com,^[65] jsou k dispozici k prokázání toho, jak kódovat a porovnávat libovolné symbolické sekvence způsobem, který plně využívá výhod moderních MapReduce distribuce vyvinutá pro cloud computing.

Porovnání metod založených na zarovnání a bez zarovnání

Aplikace metod bez zarovnání

• Genomické přesmyky^[67][68]
• Molekulární fylogenetika^[9][14][69]
• Metagenomika^{[70][71][72][73][74]}
• Analýza dat sekvence nové generace^[70][30]
• Epigenomika^[75]
• Čárové kódy druhů^[76]
• Populační genetika^[11]
• Horizontální přenos genů^[8]
• Sérum / genotypizace virů^[21][77][78]
• Predikce alergenity^[79]
• Objev SNP^[80]
• Detekce rekombinace^[81]

Seznam webových serverů / softwaru pro metody bez zarovnání

Viz také

• Sekvenční analýza
• Zarovnání více sekvencí
• Fylogenomika
• Bioinformatika
• Metagenomika
• Sekvenování nové generace
• Populační genetika
• SNP
• Program detekce rekombinace
• Skenování genomu

Reference