CI12

Obsah

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]

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

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$

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)

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]