ProbCons - ProbCons

ProbCons je open source pravděpodobnostní vícenásobné zarovnání založené na konzistenci aminokyselina sekvence. Je to jeden z nejúčinnějších proteinů vícenásobné zarovnání sekvence programy, protože opakovaně prokázal statisticky významnou výhodu v přesnosti oproti podobným nástrojům, včetně Clustal a MAFFT.^[1]^[2]

Algoritmus

Následující text popisuje základní osnovu algoritmu ProbCons.^[3]

Krok 1: Spolehlivost zarovnávací hrany

Pro každou dvojici sekvencí spočítejte pravděpodobnost, že písmena ${displaystyle x_ {i}}$ a ${displaystyle y_ {i}}$ jsou spárovány ${displaystyle a ^ {*}}$ zarovnání, které je generováno modelem.

${displaystyle {egin {aligned} P (x_ {i} sim y_ {i} | x, y) & {stackrel {def} {=}} Pr [x_ {i} sim y_ {i} {ext {v některých }} | x, y] & = součet _ {{ext {zarovnání a s}} x_ {i} -y_ {i}} Pr [a | x, y] & = součet _ {ext {zarovnání a} } mathbf {1} {x_ {i} -y_ {i} v a} Pr [a | x, y] konci {zarovnáno}}}$

(Kde ${displaystyle mathbf {1} {x_ {i} sim y_ {i} in a}}$ se rovná 1, pokud ${displaystyle x_ {i}}$ a ${displaystyle y_ {i}}$ jsou v zarovnání a jinak 0).

Krok 2: Maximální očekávaná přesnost

Přesnost zarovnání ${displaystyle a ^ {*}}$ s ohledem na jiné vyrovnání ${displaystyle a}$ je definován jako počet běžných zarovnaných párů děleno délkou kratší sekvence.

Vypočítejte očekávanou přesnost každé sekvence:

${displaystyle {egin {aligned} E_ {Pr [a | x, y]} (acc (a ^ {*}, a)) & = součet _ {a} Pr [a | x, y] acc (a ^ { *}, a) & = {frac {1} {min (| x |, | y |)}} cdot sum _ {a} mathbf {1} {x_ {i} sim y_ {i} v a} Pr [a | x, y] & = {frac {1} {min (| x |, | y |)}} cdot součet _ {x_ {i} -y_ {i}} P (x_ {i} sim y_ {j} | x, y) konec {zarovnáno}}}$

Tím se získá zarovnání s maximální očekávanou přesností (MEA):

${displaystyle E (x, y) = arg max _ {a ^ {*}}; E_ {Pr [a | x, y]} (acc (a ^ {*}, a))}$

Krok 3: Pravděpodobnostní transformace konzistence

Všechny páry sekvencí x, y ze sady všech sekvencí ${displaystyle {mathcal {S}}}$ jsou nyní přehodnoceny pomocí všech přechodných sekvencí z:

${displaystyle P '(x_ {i} -y_ {i} | x, y) = {frac {1} {| {mathcal {S}} |}} součet _ {z} součet _ {1leq kleq | z |} P (x_ {i} sim z_ {i} | x, z) cdot P (z_ {i} sim y_ {i} | z, y)}$

Tento krok lze iterovat.

Krok 4: Výpočet vodicího stromu

Vytvořte strom průvodce hierarchickým seskupováním pomocí skóre MEA jako skóre podobnosti sekvence. Klastrová podobnost je definována pomocí váženého průměru přes podobnost párové sekvence.

Krok 5: Vypočítejte MSA

Nakonec vypočítejte MSA pomocí progresivního zarovnání nebo iteračního zarovnání.

Viz také

Reference

^ Do CB, Mahabhashyam MS, Brudno M, Batzoglou S (2005). „PROBCONS: Pravděpodobnostní konzistence založené na vícenásobném sekvenčním zarovnání“. Výzkum genomu. 15 (2): 330–340. doi:10,1101 / gr. 2821705. PMC 546535. PMID 15687296.
^ Roshan, Usman (01.01.2014). Msgstr "Vícenásobné seřazení sekvencí pomocí Probcons a Probalign". V Russell, David J (ed.). Více metod zarovnání sekvence. Metody v molekulární biologii. 1079. Humana Press. str. 147 鈥 . doi:10.1007/978-1-62703-646-7_9. ISBN 9781627036450. PMID 24170400.
^ Přednáška „Bioinformatika II“ na univerzitě ve Freiburgu

externí odkazy

Oficiální webové stránky

[1] Do CB, Mahabhashyam MS, Brudno M, Batzoglou S (2005). „PROBCONS: Pravděpodobnostní konzistence založené na vícenásobném sekvenčním zarovnání“. Výzkum genomu. 15 (2): 330–340. doi:10,1101 / gr. 2821705. PMC 546535. PMID 15687296.

[2] Roshan, Usman (01.01.2014). Msgstr "Vícenásobné seřazení sekvencí pomocí Probcons a Probalign". V Russell, David J (ed.). Více metod zarovnání sekvence. Metody v molekulární biologii. 1079. Humana Press. str. 147 鈥 . doi:10.1007/978-1-62703-646-7_9. ISBN 9781627036450. PMID 24170400.

[3] Přednáška „Bioinformatika II“ na univerzitě ve Freiburgu

[1]

[2]

[3]