1-BIN-301, 2-AIN-501 Methods in Bioinformatics, 2023/24

Introduction · Rules · Tasks and dates · Materials · Moodle
Quizzes can be found in Moodle.
Homework assignments and journal club papers can be found in Tasks and dates.
Exam rules, example questions and syllabus
Groups for journal club have each their own group in Moodle.


CI12

Z MBI
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]

Iný príklad: Zarovnanie sekvencií RNA so štruktúrou

Máme dané dve sekvencie RNA a pre každú z nich máme daný zoznam párov báz (pozícií v rámci sekvencie), ktoré by mohli byť prítomné v sekundárnej štruktúre.

  • Zoznam párov môže byť konkrétna známa sekundárna štruktúra danej sekvencie alebo väčšia množina párov, ktoré by sa v štruktúre mohli vyskytovať, napríklad dvojice, ktoré majú pomerne veľkú pravdepodobnosť byť spárené v SCFG modeli alebo dokonca všetky dvojice komplementárnych báz.

Cieľom je nájsť optimálne zarovnanie týchto dvoch sekvencií, v ktorom použijeme obvyklé skórovanie zhôd, nezhôd a medzier, ale navyše pridáme nejaké skóre za zhody v štruktúre. Dva potenciálne páry, každý z jednej sekvencie, považujeme za zarovnané, ak sú navzájom zarovnané bázy na ich obidvoch koncoch. Do skórovania vyberieme podmnožinu zarovnaných párov tak, aby každá báza bola v najviac jednom páre a každému takému páru priradíme nejaké kladné skóre.

Detaily: https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-8-271