1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2021/22

Introduction · Rules · Tasks and dates · Materials · Moodle · Discussion


CI12: Rozdiel medzi revíziami

Z MBI
Prejsť na: navigácia, hľadanie
(Prakticke programy na NP tazke problemy)
(ILP)
 
Riadok 13: Riadok 13:
  
 
===ILP===
 
===ILP===
'''Linearny program:'''  
+
'''Lineárny program:'''  
* Mame realne premenne x_1...x_n, minimalizujeme nejaku ich linearnu kombinaciu <math>\sum_i a_i x_i\,</math> kde a_i su dane vahy.
+
* Mame reálne premenné x_1...x_n, minimalizujeme nejaku ich linearnu kombinaciu <math>\sum_i a_i x_i\,</math> kde a_i su dane vahy.
 
* Mame tiez niekolko podmienok v tvare linearnych rovnosti alebo nerovnosti, napr. <math>\sum_i b_i x_i \le c</math>
 
* Mame tiez niekolko podmienok v tvare linearnych rovnosti alebo nerovnosti, napr. <math>\sum_i b_i x_i \le c</math>
 
* Hladame teda hodnoty premennych, ktore minimalizuju cielovu sumu, ale pre ktore platia vsetky podmienky
 
* Hladame teda hodnoty premennych, ktore minimalizuju cielovu sumu, ale pre ktore platia vsetky podmienky

Aktuálna revízia z 13:10, 10. december 2020

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]