1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2022/23

Introduction · Rules · Tasks and dates · Materials · Moodle · Discussion
Quizzes can be found in Moodle.
Homework assignments and journal club papers can be found in Tasks and dates.
Groups for journal club have each their own channel in MS Teams.


CI12

Z MBI
Revízia z 12:10, 10. december 2020; Brona (Diskusia | príspevky)

(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
Prejsť na: navigácia, hľadanie

Protein threading

Praktické programy na NP ťažké problémy

  • 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, tiež Lingeling, glucose, CryptoMiniSat, painless
  • Concorde TSP solver [6] - riesi problem obchodneho cestujuceho so symetrickymi vzdialenostami, zadarmo na akademicke ucely
    • Pre zaujimavost: TSP art [7]

ILP

Lineárny program:

  • Mame reálne premenné 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]