Probalign - Probalign - Wikipedia

Probalign je nástroj pro zarovnání sekvence, který vypočítá maximum očekávaná přesnost zarovnání pomocí rozdělení funkcí zadní pravděpodobnosti.^[1] Pravděpodobnosti základních párů se odhadují pomocí odhadu podobného jako Boltzmannova distribuce. Funkce oddílu se vypočítá pomocí a dynamické programování přístup.

Algoritmus

Následující text popisuje algoritmus používaný probalignem k určení pravděpodobností párů bází.^[2]

Skóre zarovnání

Ke skórování zarovnání dvou sekvencí jsou potřeba dvě věci:

• funkce podobnosti ${ displaystyle sigma (x, y)}$ (např. PAM, BLOSUM,...)
• pokuta za afinní mezeru: ${ displaystyle g (k) = alfa + beta k}$

Skóre ${ displaystyle S (a)}$ zarovnání a je definována jako:

${ displaystyle S (a) = součet _ {x_ {i} -y_ {j} v a} sigma (x_ {i}, y_ {j}) + { text {cena mezery}}}$

Nyní je boltzmann vážené skóre zarovnání a:

${ displaystyle e ^ { frac {S (a)} {T}} = e ^ { frac { součet _ {x_ {i} -y_ {j} v a} sigma (x_ {i}, y_ {j}) + { text {gap cost}}} {T}} = left ( prod _ {x_ {i} -y_ {i} in a} e ^ { frac { sigma (x_ {i}, y_ {j})} {T}} vpravo) cdot e ^ { frac {gapcost} {T}}}$

Kde ${ displaystyle T}$ je měřítko.

Pravděpodobnost vyrovnání za předpokladu boltzmannova rozdělení je dána vztahem

${ displaystyle Pr [a | x, y] = { frac {e ^ { frac {S (a)} {T}}} {Z}}}$

Kde ${ displaystyle Z}$ je funkce oddílu, tj. součet boltzmannových vah všech zarovnání.

Dynamické programování

Nechat ${ displaystyle Z_ {i, j}}$ označuje funkci oddílu předpon ${ displaystyle x_ {0}, x_ {1}, ..., x_ {i}}$ a ${ displaystyle y_ {0}, y_ {1}, ..., y_ {j}}$. Jsou zvažovány tři různé případy:

1. ${ displaystyle Z_ {i, j} ^ {M}:}$ funkce rozdělení všech zarovnání dvou předpon, které končí shodou.
2. ${ displaystyle Z_ {i, j} ^ {I}:}$ funkce rozdělení všech zarovnání dvou předpon, které končí vložením ${ displaystyle (-, y_ {j})}$.
3. ${ displaystyle Z_ {i, j} ^ {D}:}$ funkce rozdělení všech zarovnání dvou předpon, které končí odstraněním ${ displaystyle (x_ {i}, -)}$.

Pak máme: ${ displaystyle Z_ {i, j} = Z_ {i, j} ^ {M} + Z_ {i, j} ^ {D} + Z_ {i, j} ^ {I}}$

Inicializace

Matice jsou inicializovány následovně:

• ${ displaystyle Z_ {0, j} ^ {M} = Z_ {i, 0} ^ {M} = 0}$
• ${ displaystyle Z_ {0,0} ^ {M} = 1}$
• ${ displaystyle Z_ {0, j} ^ {D} = 0}$
• ${ displaystyle Z_ {i, 0} ^ {I} = 0}$

Rekurze

Funkce rozdělení pro zarovnání dvou sekvencí ${ displaystyle x}$ a ${ displaystyle y}$ je dána ${ displaystyle Z_ {| x |, | y |}}$, které lze rekurzivně vypočítat:

• ${ displaystyle Z_ {i, j} ^ {M} = Z_ {i-1, j-1} cdot e ^ { frac { sigma (x_ {i}, y_ {j})} {T}} }$
• ${ displaystyle Z_ {i, j} ^ {D} = Z_ {i-1, j} ^ {D} cdot e ^ { frac { beta} {T}} + Z_ {i-1, j} ^ {M} cdot e ^ { frac {g (1)} {T}} + Z_ {i-1, j} ^ {I} cdot e ^ { frac {g (1)} {T} }}$
• ${ displaystyle Z_ {i, j} ^ {I}}$ analogicky

Pravděpodobnost základního páru

Nakonec pravděpodobnost, že pozice ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {j}}$ tvoří základní pár je dán vztahem:

${ displaystyle P (x_ {i} -y_ {j} | x, y) = { frac {Z_ {i-1, j-1} cdot e ^ { frac { sigma (x_ {i}, y_ {j})} {T}} cdot Z '_ {i', j '}} {Z_ {| x |, | y |}}}}$

${ displaystyle Z ', i', j '}$ jsou příslušné hodnoty přepočítaných ${ displaystyle Z}$ s převrácenými řetězci párů bází.

Viz také

• ProbCons
• Zarovnání více sekvencí

Reference

externí odkazy

• Probalign Webservice