Probalign

Probalign är ett sekvensjusteringsverktyg som beräknar en maximal förväntad noggrannhetsjustering med hjälp av partitionsfunktionens posteriora sannolikheter. Basparssannolikheter uppskattas med en uppskattning som liknar Boltzmann-fördelningen . Partitionsfunktionen beräknas med en dynamisk programmeringsmetod .

Algoritm

Följande beskriver algoritmen som används av probalign för att bestämma basparsannolikheterna.

Uppriktningspoäng

För att göra en anpassning av två sekvenser behövs två saker:

• en likhetsfunktion $\sigma (x,y)$ (t.ex. PAM , BLOSUM ,...)
• affin gap penalty: $g(k)=\alpha +\beta k$

Poängen $S(a)$ för en anpassning a definieras som:

$S(a)=\summa _{x_{i}-y_{j}\in a}\ sigma (x_{i},y_{j})+{\text{gap cost}}$

Nu är den viktade boltzmann-poängen för en inriktning a:

$e^{\frac {S(a)}{T}}=e^{\frac {\sum _{x_{i}-y_{j}\in 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}}\right)\cdot e^{\frac {gapcost}{T}}$

Där $T$ är en skalningsfaktor.

Sannolikheten för en inriktning under antagande av boltzmann-fördelning ges av

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

Där $Z$ är partitionsfunktionen, dvs summan av boltzmannvikterna för alla linjer.

Dynamisk programmering

Låt $Z_{i,j}$ beteckna partitionsfunktionen för prefixen $x_{0},x_{1},...,x_{i}$ och $y_{0},y_{1},...,y_{j}$ . Tre olika fall beaktas:

1. $Z_{i,j}^{M}:$ partitionsfunktionen för alla justeringar av de två prefixen som slutar i en matchning.
2. $Z_{i,j}^{I}:$ partitionsfunktionen för alla justeringar av de två prefixen som slutar med en infogning $(-,y_{ j})$ .
3. $Z_{i,j}^{D}:$ partitionsfunktionen för alla justeringar av de två prefixen som slutar med en radering $(x_{i} ,-)$ .

Då har vi: $Z_{i,j}=Z_{i,j}^{M}+Z_{i ,j}^{D}+Z_{i,j}^{I}$

Initialisering

Matriserna initieras enligt följande:

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

Rekursion

Partitionsfunktionen för justeringarna av två sekvenser $x$ och $y$ ges av $Z_{|x|,|y|}$ , som kan beräknas rekursivt:

• $Z_{i,j}^{M}=Z_{i-1,j-1}\ cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}$
• $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}}$
• $Z_{i,j}^{I}$ analogt

Sannolikhet för baspar

Slutligen ges sannolikheten att positionerna $x_{i}$ och $y_{j}$ bildar ett baspar av:

$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|}}}$

$Z',i',j'$ är respektive värden för den omräknade $Z$ med inverserade basparsträngar.

Se även

• ProbCons
• Multiple Sequence Alignment

externa länkar

• Probalign Webservice