Introduction

Въведение в предмета чрез една по-сложна задача


подлежи на бъдещо дописване


Задачата за Contact Map Overlap

Малко предисловие - в страницата се съдържат термини от теорията на графите, които ще бъдат разяснени в следващите глави от предмета.
Започваме с една интересна задача от малко по-различна сфера - микро биологията. Интересното в тази задача е, че може да се сведе до задача за графи и още по-интересно - най-успешните подходи за атакуване на въпросната задача са именно чрез използването на графи.
Ето и самият проблем. Според молекулярната биология, качествата на даден протеин са в тясна връзка със неговата форма в 3D пространството. От години насам учени се опитват да класифицират различните протеини (хиляди на брои) според общите им качества. До тук добре, проблемът възниква когато трябва да се определи колко "близки" са два протеина само според сложната форма, която са заели. И тук, доста неочаквано, се намесва дискретната математика…

Ето и стъпките, по които трансформираме нашето грозно пате (така де, кой се кефи на микробиология?!) в проблем от теорията на графите.
Както не е ясно колко от вас знаят, протеините са създадени от аминокиселини (основните са 20 на брой ), те образуват сложни връзки и странни форми, и именно те ще са върховете в нашия граф. До тук добре, но ни трябва и релация. Релацията в нашия случай е "близост" на отделните молекули, или каквото се водят, аминокиселини в състава на даден протеин. Ако две такива аминокиселинни молекули се считат за достатъчно "близки" (или на достатъчно малко разстояние) в структурата на даден протеин, то считаме че те са в релация.
За всеки протеин си има специфичен и уникален начин за представяне на неговия строеж, наречен contact map, посредством малко по-странно изобразен граф.

grafi3lq6.jpg

Чрез contact map-a ние получихме един много опростен модел на 3D структурата на протеина, сега вече може да пристъпим и към първоначално поставената задача. Нека номерираме нашите върхове(аминокиселини) в contact map-a с естествените числа от 1 до n. Нека и дефинираме функцията z, която за дадени два протеина ни дава величина съответстваща на "близостта", нека z е 0 в началото. Вече нашата задача се състои в следното: По дадени 2 contact map-a, съответно на два различни протеина, да се вземе по един подграф (по-късно ще дефинираме това и още много други понятия…), да създадем дъги между връх от единия и връх от другия подграф с три важни условия:
1. От всеки връх излиза най-много една дъга;
2. Ако разпишем нашите contact map-ове на 2 последователни реда, нека единият е с n a другият с m върха, да нямаме пресичане на дъги;
3. Ако има релация между i-ия и j-ия елемент от първия map и релация между k-ия и l-ия елемент от втория map и ние изберем точно тези четири елемента да участват в съответните подграфи, с дъги между i-ия и k-ия и между j-ия и l-ия (дъгите отговарят на условия 1 и 2), то тогава увеличаваме z с 2 (или някакво положително цяло число);
При така поставените условия остава да дефинираме само какво се търси, а то е: Да се намери максималната стойност на z при дадени два протеина.

Ако условие 2 липсваше, то задачата би била лесна, тъй като вече съществува полиномиален алгоритъм който да я реши (Network flow - за по-любознателните). При наличието на условие 2 обаче, нашата задача става NP-complete (или hard, подробности…). За какво тогава се борим? Ами оказва се че една задача може да се представи по безброй много различни начина и да се сведе до безброй много други задачи, някои от които по-понятни и по-лесни за атака (figure of speach).

Примерни подходи към задачата

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License