1-BIN-301, 2-AIN-501 Metódy v bioinformatike, ZS 2018/19

Úvod · Pravidlá · Termíny a zadania · Prednášky a poznámky · Facebook (oznamy a diskusie) (návod a pravidlá)
Zadania domácich úloh a články na journal club nájdete v časti Termíny a zadania.
Pozrite si ukážkové príklady na skúšku.
Rozpis skupín pre journal club je zverejnený.


CI12

Z MBI
Prejsť na: navigácia, hľadanie

Protein threading

Prakticke programy na NP tazke problemy

  • Obcas chceme najst optimalne riesenie nejakeho NP-tazkeho problemu
  • Jedna moznost je previest na iny NP tazky problem, pre ktory existuju pomerne dobre prakticke programy, napriklad integer linear programming (ILP)
  • najdu optimalne riesenie, mnohe instancie zrataju v rozumnom case, ale mozu bezat aj velmi dlho
  • CPLEX [1] a Gurobi [2] komercne baliky na ILP, akademicka licencia zadarmo
  • SCIP [3] nekomercny program pre ILP
  • SYMPHONY v projekte COIN-OR [4]
  • Minisat [5] open source SAT solver
  • Concorde TSP solver [6] - riesi problem obchodneho cestujuceho so symetrickymi vzdialenostami, zadarmo na akademicke ucely
    • Pre zaujimavost: TSP art [7]

ILP

Linearny program:

  • Mame realne premenne x_1...x_n, minimalizujeme nejaku ich linearnu kombinaciu \sum _{i}a_{i}x_{i}\, kde a_i su dane vahy.
  • Mame tiez niekolko podmienok v tvare linearnych rovnosti alebo nerovnosti, napr. \sum _{i}b_{i}x_{i}\leq c
  • Hladame teda hodnoty premennych, ktore minimalizuju cielovu sumu, ale pre ktore platia vsetky podmienky
  • Da sa riesit v polynomialnom case

Integer linear program

  • Program, v ktorom vsetky/vybrane premenne musia mat celociselne hodnoty, alebo dokonca povolime iba hodnoty 0 a 1.
  • NP uplny problem

Ako zapisat (NP-tazke) problemy ako ILP

Knapsack

  • Problem: mame dane predmety s hmotnostami w_1..w_n a cenami c_1..c_n, ktore z nich vybrat, aby celkova hmotnost bola najviac T a cena bola co najvyssia?
  • Pouzijeme binarne premenne x_1..x_n, kde x_i = 1 prave vtedy ked sme zobrali i-ty predmet.
  • Chceme maximalizovat \sum _{i}c_{i}x_{i}\,
  • za podmienky ze \sum _{i}w_{i}x_{i}\leq T

Set cover:

  • Mame n mnozin S_1...S_n nad mnozinou {1...m}. Chceme vybrat co najmensi pocet zo vstupnych mnozin tak, aby ich zjednotenie bola cela mnozina {1..m}
  • Binarne premenne x_i=1 ak vyberieme i-tu mnozinu
  • Chceme minimalizovat \sum _{{i=1}}^{n}x_{i}\,
  • za podmienky, ze pre kazde j z {1..m} plati \sum _{{i:j\in S_{i}}}x_{j}\geq 1

Protein threading

  • Ciel: protein A ma znamu sekvenciu aj strukturu, protein B iba sekvenciu. Chceme zarovnat proteiny A a B, pricom budeme brat do uvahy znamu strukturu, t.j. ak su dve amino kyseliny blizko v A tak ich ekvivalenty v B by mali byt "kompatibilne".
  • Tento problem chceme riesit tak, ze v strukture A urcime nejake jadra, ktore by v evolucii mali zostat zachovane bez inzercii a delecii a v rovnakom poradi. Tieto jadra su oddelene sluckami, ktorych dlzka sa moze lubovolne menit a ktorych zarovnania nebudeme skorovat.
  • Formulacia problemu: Mame danu sekvenciu B=b1..bn, dlzky m jadier c_1...c_m a skorovacie tabulky E_ij, ktora vyjadruje, ako dobre bj..b_{j+c_i-1} sedi do sekvencie jadra i a E_ijkl ktora vyjadruje, ako dobre by jadra i a k interagovali, keby mali sekvencie zacinajuce v B na poziciach j a l. Uloha je zvolit polohy jadier x_1<x_2<...<x_m tak, aby sa ziadne dve jadra neprekryvali a aby sme dosiahli najvyssie skore.
  • Poznamka: nevraveli sme, ako konkretne zvolit jadra a skorovacie tabulky, co je modelovaci, nie algoritmicky problem (mozeme skusit napr. nejake pravdepodobnostne modely)

Protein threading ako ILP

  • Premenne v programe:
    • x_ij=1 ak je zaciatok i-teho jadra zarovnane s b_j
    • y_ijkl=1 ak je zaciatok i-teho jadra na b_j a zaciatok k-teho na b_l (i<k, j<l)
  • Chceme maximalizovat \sum E_{{ij}}x_{{ij}}+\sum E_{{ijkl}}y_{{ijkl}}
  • Podmienky:
    • \sum _{j}x_{{ij}}=1\, pre kazde i
    • x_{{il}}+x_{{i+1,k}}\leq 1 pre vsetky i,k,l, kde k<l+c_i
    • y_{{ijkl}}\leq x_{{ij}} pre vsetky i,j,k,l, kde i<k, j<l
    • y_{{ijkl}}\leq x_{{kl}} pre vsetky i,j,k,l, kde i<k, j<l
    • y_{{ijkl}}\geq x_{{ij}}+x_{{kl}}-1 pre vsetky i,j,k,l, kde i<k, j<l

Na zamyslenie:

  • Aka bude velkost programu ako funkcia n a m?
  • Co ak nie vsetky jadra navzajom interaguju? Mozeme na velkosti programu usetrit?
  • Preco asi vobec autori zaviedli jadra a ako by sme zmenili program, ak by sme chceli uvazovat kazdu aminokyselinu zvlast?

Zdroj:

  • Jinbo Xu, Ming Li, Dongsup Kim, and Ying Xu. "RAPTOR: optimal protein threading by linear programming." Journal of bioinformatics and computational biology 1, no. 01 (2003): 95-117. [8]

Gibbsovo vzorkovanie na určenie štruktúry populácie

  • Nerobili sme, uvedene pre zaujimavost (Gibbsovo vzorkovanie vid. hladanie motivov, CI09)

Gibbs sampling, Gibbsovo vzorkovanie všeobecne

  • Cielove rozdelenie ma n premennych \pi (x_{1},...x_{n})
  • V kazdom kroku vzorkujeme jednu premennu z podmienenej pravdepodobnosti \Pr(x_{i}|x_{1},\dots ,x_{{i-1}},x_{{i+1}},\dots x_{n})
  • Ostatne hodnoty nechame rovnake ako v predchadzajucom kroku
  • Premennu x_{i} zvolime nahodne alebo periodicky i=1,2,\dots ,n
  • Vzorky nie su nezavisle, no vieme dokazat nieco o konvergencii k \pi (pozri nizsie)

Markov chain Monte Carlo MCMC

  • Chceme generovať náhodné vzorky z nejakeho cieloveho rozdelenia \pi , ale toto rozdelenie prilis zlozite.
  • Zostavime ergodicky Markovov retazec, ktoreho stacionarne rozdelenie je rozdelenie \pi , tak aby sme efektivne vedeli vzorkovat X_{{t}} ak vieme X_{{t-1}}.
  • Ak zacneme z lubovolneho bodu, po urcitom case t rozdelenie X_{{t}} priblizne \pi
  • Ale za sebou iduce vzorky nie su nezavisle!
  • Vieme vsak odhadovat ocakavane hodnoty roznych velicin {\frac  {1}{t}}\sum _{{i=1}}^{t}f(X_{t}) konverguje k E_{\pi }[f(X)]

Určovanie štruktúry populácie


  • Majme N haploidnych jedincov (lahko sa rozsiri aj na genotypy pri diploidnych jedincoch), L genotypovanych SNPov, SNPy navzajom nezavisle (v stave LE), pocet populacii K
  • X[i,l] - haplototyp jedinca i v SNPe l (zvacsa binarna premenna)
  • Z[i,l] - z ktorej subpopulacie pochadza alela X[i,l] (cislo z {1...k})
  • Q[i,k] - aka cast genomu jedinca i pochadza z populacie k (realne cislo)
  • P[k,l,a] - frekvencia alely a v SNPe l v populacii k (realne cislo)
  • P pochadza z nejakeho apriorneho rozdelenia, napr. rovnomerne rozdelenie, Dirichletovo rozdelenie, nezavisle pre kazde k,l
  • Podobne Q (nezavisle pre kazde i)
  • Pr(Z[i,l] = k|P,Q) = Q[i,k] a Pr(Z|P,Q) je sucin takychto clenov
  • Pr(X[i,l] = a|Z,P,Q) = P[Z[i,l],l,a] a Pr(X|Z,P,Q) je sucin takychto clenov (SNPy nezavisle)
  • To nam urcuje Pr(P,Q,Z,X) = Pr(P)Pr(Q)Pr(Z|P,Q)Pr(X|Z,P,Q)
  • My chceme Pr(Q|X)

Algoritmus Gibbsovho vzorkovania:

  • Zvol pociatocne Z^{{(0)}}
  • Opakuj:
    • Zvol nahodne P^{{(m)}},Q^{{(m)}} z Pr(P,Q|X,Z^{{(m-1)}})
    • Zvol nahodne Z^{{(m)}} z Pr(Z|X,P^{{(m)}},Q^{{(m)}})
  • Vzorce v clanku
  • Mierna komplikacia: ak aproximujeme E[Q[i,k]|X] pomocou priemeru Q^{{(m)}}, mali by sme dostat 1/K kvoli symetrii (K! symetrickych rieseni)
  • Nastastie sa Gibbsovo vzorkovanie malokedy presuva medzi roznymi oznackovaniami tych istych populacii
  • Inak musime nejako preznacit populacie vo vysledku, aby boli ekvivalentne v roznych vzorkach