Дискретна Оптимизация - Тема 1

Увод


страницата се нуждае от дописване/преглеждане


Задачата protein threading

Това е проблем, възникнал в областта на биологията. Става дума за разположението на аминокиселини в пространството (3тична структура на белтък) по дадена двоична структура. За да опростим максимално проблема, за целта на тази уводна лекция ще приемем, че решаваме следната задача:

  • Дадени са N на брой клетки
  • Дадени са m на брой аминокиселини в точно определена последователност. Всяка аминокиселина има положителна дължина $l_1, l_2, \cdots, l_m$
  • Трябва да се разположат mте аминокиселини една след друга в Nте клетки. Разбира се, всяка аминокиселина започва след края на предходната, и редът им е фиксиран (не може да се разместват - само да се приплъзват напред-назад из клетките, запазвайки същия относителен ред)

Математически модел

Вече имаме задача от областта на биологията. За да започнем решаването й като математици, се нуждаем от математически модел. Това означава да сведем задачата до някаква математическа такава (система уравнения/неравенства, диференциране/интегриране и т.н.), след решаването на която, можем (сравнително) лесно да получим и решение на оригиналната задача.

реален проблем математически модел
Мястото на всяка аминокиселина еднозначно се определя от номера на първата клетка, която тя заема. $x_1, x_2, \cdots, x_m \quad x_i \in \{1, 2, \cdots N\}$
Тъй като всяка една аминокиселина започва след следващата (т.е няма застъпване) трябва да е изпълнено и следното условие: началото на дадена киселина + дължината и трябва да е по-малко или равно на началото на следващата. $x_i + l_i \le x_{i+1} \quad \forall i = \overline{1,m-1}$
На всяко едно разпределение ще съпоставим цена, която определя до колко това разпределение е невероятно за срещане в природата. Нашата цел ще бъде да минимизираме тази цена, с цел да получим истинското подреждане на аминокиселините. Ако приемем, че $c_{ik}$ е цената за поставяне на iтата аминокиселина на kта позиция, то тогава трябва да оптимизираме следната функция $f = \min \sum_{i = 1}^m c_{ix_i}$

Усложняване на задачата

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