В этой части мы поговорим о том, как можно так сократить число поворотов цепи, чтобы сократить рассчеты, но при этом не потеряв возможность попадания в нужные состояния.
Но вначале хочу обратиться к специалистам в этой области:
Вначале развею возможное недопонимание: я любитель, и не занимаюсь этой темой профессионально. Я заметил, что тут есть специалисты в этой теме. Странно, что я не читаю ваших статей, а вы читаете мои. Очень надеюсь, что эта ситуация поменяется. Я хочу почитать ваши статьи, и желательно написанные простым языком, и где вы даете ответы, а не отправляете в известном направлении в гугл. Просто у меня есть некий негативный опыт, когда только начинал ряд специалистов, которых удавалось находить в интернете делали умный вид и не помогали словом, и делом — а отправляли в указанном направлении. Здесь я пытаюсь рассказать свой маленький опыт — но может это позволит кому-то легче стартовать.
Тем же кто желает тут похоливарить. Давайте так. Я такой любитель — которому погоны специалистов значут мало, а наука такое дело требует повторяемости (а не бизнес-скрытности, это же не бизнес, чтобы скрывать детали своих алгоритмов и не публиковать их код?), поэтому просто разговоры меня интересуют мало. Но меня очень интересует когда мне показывают, что я занимаюсь немного не тем, и что есть люди которые действительно чего-то добились. Вот задача над которой я мучаюсь. Решите и покажите, что это просто — буду очень благодарен.
Я даю произвольную (реально существующую) первичную последовательность до 100 нуклеотидов. Указываю все водородные связи которые нужно образовать. Вы на выходе даете мне файл .pdb, в котором третичная структура из указанной первичной последовательности и где образованы все требуемые водородные связи. Ни каких других требований.
Прошу или показать, что это просто или ответственно подтвердить, что эта задача скажем за неделю (или другой разумный срок) — не решается.
Ну, а пока этого нет и нет ваших статей, например, о других подходах, вроде молекулярной динамики и т.д., извольте читать о предлагаемом мной подходе и критиковать конструктивно, помогать своими знаниями, участвовать в обсуждении проблемы и может быть даже объединить со мной усилия и чего-то сделать вместе.
И снова моей аудитории, которая не является специалистами: важно поверить, что это легко, и не обязательно знать физику, биологию, и сложную математику — надеюсь вы умеете программировать и этого достаточно. Выше кстати, задача, которую мы и будем решать… но не все сразу. По плюсам — я понял что Вы читаете. Но неужели все понятно и нет вопросов? Если что жду комментариев, даже самых наивных. Пора делать эту область исследований хотя бы простой по описанию, а не скрывать ее за не нужными тонами сложностей.
Итак. Сегодня план простой — надо сократить разумно число поворотов, которые будем просчитывать. Есть два способа (не вообще, а в моем кибернетико-геометрическом подходе).
Способ №1. Сравнительно простой. Вообще если поворачивать с точностью 0.1 градус, то есть 3600 вариантов поворота. Но как правило когда цепь уже имеет несколько водородных связей, у нее не очень большая свобода поворота. Поэтому можно взять от текущего угла ± 5 градусов, и тогда нужно проверить только 100 вариантов. Если нужно повернуться больше, чем на 5 градусов — то это произойдет на следующей итерации.
Первый способ может ограниченно применяться когда цепь уже имеет ряд водородных связей, и приняла более менее правильное состояние. Если его применить к начальному состоянию цепи — вытянутой цепи, то этот способ очень быстро приведет к локальному минимуму. Помните в первой статье 5 шагов сворачивания цепи на картинке. Так вот цепь так свернется до 5 шага, и потом не сможет занять нормальное состояние, алгоритм зациклится.
Способ №2. Этот способ был навеян мне статьей Rhiju Das and David Baker, «Automated de novo prediction of native-like RNA tertiary structures», University of California, Berkeley, CA, 2007. Я с течением времени несколько усовершенствовал и вот рассказываю. Rhiju Das предложил интересную идею. Как так выгодно поворачивать сразу по нескольким углам, чтобы комбинация этих углов была выгодной? Он решил подсмотреть у природы, и это очень правильно. Тут описывалось, что получена 3D-модель рибосомы на атомном уровне. Так вот рибосома состоит не только из белков, а в своей основе, как платформе на которую потом укладываются белки, содержит две рибосомальных РНК. Одна из них самая большая содержит 2700 нуклеотидов. Она получена в биоэксперименте. Rhiju Das составил базу данных углов, которые бывают в этой рибосоме = 9*2700 углов. Если различать пурины (a, g) и пиримидины (u,c), то имеем примерно по 1500 вариантов. Тогда скажем хотим повернуть комбинацию двух углов №1 и №6 (кратко запишем 16) — берем из базы данных подходящие 1500 углов и поворачиваем. И это удивительно дает неплохие результаты, хотя проворачиваем совсем другую цепь РНК.
Дальше уже в следующей статье нам нужно будет говорить о т.н. целевой функции, т.е. как оценивать сделали мы хороший поворот или нет. Тут мой кибернетический подход несколько революционный. Я всюду встречал, что основываются только на энергию цепи. Или вычисляя максимально близко физически или делает математическую прикидку.
Почему я пошел по другому пути? Даю вначале один слайд:
Конечно это несколько утрировано. Но не далеко от истины. Вы видите две структуры цепи — оценка энергии для них дает очень близкие значения. Но вы видите как структуры различны? Одна сразу видно по рисунку — биологически неправдоподобна. Именно поэтому визуализация тут очень важна, компьютер может долго заниматься расчетами, считая что-то «хорошим» состоянием. Но если в такое «биологически неправильное» состояние попали расчеты — то уже практически нет шанса остановить алгоритм и выбраться из локального решения перейдя к худшему по оценке энергии, но более биологически верному. Именно поэтому в игре FoldIt у человека больший шанс, чем у компьютерного автомата. Человек видит, примерно представляет как может быть свернута цепь и не будет искать тогда, когда видит, что глубоко попал в локальный минимум.
Так же учитывайте, что оценка или даже физический расчет энергии — это достаточно долго, сложно — но главное отличие биологически возможной от биологически несостоятельной структуры находятся в приделах погрешности расчетов.
И это проблема. Специалисты тут со мной наверняка начнут спорить — приводите конкретные данные, не тратьте мое время на холивар.
Поэтому в своей статье я пишу:
используется метод Монте-Карло для выбора позиции и углов поворота из дискрет-
ного множества, осуществляется поворот, и на основании оценки функции энергии решается, спо-
собствует ли данный поворот укладке в стабильное состояние. Если энергия понижается, то спо-
собствует, и далее исходим из этого состояния. Если нет – сделанный поворот отменяется. Таким
образом, осуществляется несколько миллионов случайных поворотов, после чего получается тре-
тичная структура с минимальной оценкой энергии, являющаяся моделью соответствующей РНК.В аналогичных компьютерных экспериментах может различаться способ дискретизации
поворотов и точность функции оценки энергии, но принципы поиска остаются такими же. Но
при использовании вышеописанного подхода имеется два существенных недостатка:1. Функция оценки энергии является приближенной, значения которой могут быть в пределах
погрешности расчётов.2. Вероятность на многомерной энергетической поверхности попасть в глобальный энерге-
тический минимум настолько низкая, что сопоставима с полным перебором. Таким образом,
применяя метод Монте-Карло для выбора поворотов, которые следует проверить, на самом деле
осуществляется полный перебор, только в случайном порядке. А это лишено смысла для NP-
полной задачи.
первый пункт я выше проиллюстрировал. Несостоятельность чистого метода Монте-Карло, а также алгоритмов в которых происходит похожие — например, генетические алгоритмы, Q-обучение, градиентные поиски и т.д. — будем обсуждать по желанию — это для меня не центральная тема. Но думаю, если подумаете поймете, что случайно выбирая состояние в поле, в котором только одна расщелина — вы в 99% процентах будите попадать в мелкие лужицы, и искать расщелину в ней, и не найдете. А чтобы найти расщелину случайным выбором — вам нужно делать выбор столько же раз сколько этапов и при полном переборе. И чего тогда строить хорошую мину при плохой игре?
В следующей части я опишу как я предлагаю делать оценку состояния цепи, и как искать, т.е. подойдем собственно к алгоритму поиска.
Автор: tac
