Период Пизано

Часть своего свободного времени я уделяю обучению на платформах для дистанционного обучения и прохожу разные курсы. Больше всего мне нравится Stepik.org.
На этом ресурсе можно найти много курсов для "чайников", где понятным языком объясняются разные аспекты IT (и не только).
После освоения основ язык программирования Python, я пошел дальше и поступил на курс "Алгоритмы и структуры данных" от Computer Science Center (Сейчас разделен на два: Алгоритмы: теория и практика. Методы и Алгоритмы: теория и практика. Структуры данных).

Трудности настигли на первом же уроке - "Числа Фибоначчи".
Для справки:
Числа Фибоначчи - это последовательность, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи на OEIS.

Последняя задача урока - задача на программирование повышенной сложности:
Даны целые числа n и m (1 <= n <= 1018, 2 <= m <= 105), необходимо найти остаток от деления n-го числа Фибоначчи на m. 
Memory Limit - 256 Mb
Time Limit - 5 seconds. 

Как можно догадаться, ограничения по памяти и времени не позволят наивному алгоритму пройти решение.
Немного погуглив, я наткнулся на обсуждение такого термина как "период Пизано".
Оказывается, что если составить последовательность из остатков деления чисел Фибоначчи на какое-ибо число, то остатки будут чередоваться с определенной периодичностью.
Возьмем первые тринадцать чисел - 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 - и найдем остатки деления на 4 - 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1.
Остатки чередуются с периодичностью каждые 6 членов, таким образом период Пизано для делителя 4, равен 6.

Для решения задачи, описанной ранее, прежде всего необходимо определить тот самый период, с указанным делителем.
Для этого в отдельный массив записываем остатки от деления чисел Фибоначчи на m до тех пор, пока не получим две единички идущие подряд.
Далее, для удобства, удаляем два последних числа массива.
После этого нужно найти x - остаток от деления n на период Пизано.
Ну и наконец, программа должны вывести число из массива с остатками с номером x.
Это и будет ответом задачи.


Еще информации на Вики и в OEIS.
На этом все )

Молекулярный докинг

Содержание

• Предисловие
• Зачем нужен молекулярный докинг?
• Скачивание программ
• Что делают программы?
• О энергии связывания
• Файлы с 3D структурой белка и лигандов
• Модификация белка (макромолекулы)
• Определение "коробки" докинга
• Модификация лигандов
• Создание конфигурационного файла
• Запуск Autodock Vina
• Автоматизация процесса
• Послесловие

---

Предисловие

С темой молекулярного докинга я познакомился просматривая лекции в Лектории МФТИ. Тогда я наткнулся на этот замечательный цикл от Петра Власова. Рекомендую к просмотру.

Зачем нужен молекулярный докинг?

Чтобы ответить на этот вопрос ознакомимся с терминологией. Вот что, по этому поводу, говорит Википедия:

Молекулярный докинг (или молекулярная стыковка) — это метод молекулярного моделирования, который позволяет предсказать наиболее выгодную для образования устойчивого комплекса ориентацию и положение одной молекулы по отношению к другой. 

Молекулярный докинг чаще всего используют в начальном этапе разработки новых лекарственных препаратов (Drug design).

Чтобы разработать новое лекарство, необходимо выбрать около ста молекул из сотен тысяч потенциальных кандидатов.

Молекулярное моделирование позволяет "отсеять" те молекулы (лиганды), которые слабо связываются с активным центром (акцептором) нужного нам белка. Ведь, как известно, почти все лекарственные препараты являются селективными ингибиторами определенных белков.

Я бы хотел показать как это работает на примере программы AutoDock Vina и попробуем найти ингибитор рицина - очень опасного растительного токсина.

Скачивание программ

Для работы нам нужны будут две программы:

1. MGL Tools - скачать, документация 
2. AutoDock Vina - скачать, мануал  

Оба разработаны в Научно-исследовательском институте Скриппса. Есть версии для Windows, Linux и MacOS X. Ранее программа MGL Tools называлась Autodock Tools, но, видимо, разработчики решили назвать ее в честь своей лаборатории - The Molecular Graphics Laboratory

Что делают программы?

MGL Tools нужен для подготовки лигандов к процессу докинга, а также визуализации как самого белка, так и результатов докинга.

AutoDock Vina запускается с командной строки и занимается непосредственно моделированием. Также программа требует определения файла белка, лиганда, log-файла и параметров докинга. Как пишут авторы проекта Autodock Vina является усовершенствованной и оптимизированной версией семейства программ Autodock 4. В Vina используется один из методов глобальной стохастической оптимизации – повторяющийся локальный поиск описанный Abagyan et al. В этом алгоритме последовательность шагов, принимается в соответствии с критерием Метрополиса, а локальная оптимизация достигается методом Бройден-Флетчер-Голдфарб-Шанно. Программа производит расчет энергии связывания (аффинности) низкомолекулярного вещества к части белка.

Энергия связывания = A + B + C - D, (ккал/моль)

Где A – это сумма общей межмолекулярной энергии, энергии Ван-дер-Ваальсового взаимодействия, электростатической энергии, энергии десольватации и энергии водородных связей; 

B – общая внутренняя энергия;

C – свободная энергия вращения; 

D – несвязанная энергия системы.

О энергии связывания

Зная энергию связывания (ΔG) можно вычислить константу ингибирования:

А получив константу ингибирования можно вычислить концентрацию полумаксимального ингибирования (IC50):

уравнение Ченга-Прусова

K_i — активность связывания ингибитора с реакционным субстратом, IC₅₀ — функциональные активность ингибитора, [S] — концентрация реакционного субстрата, K_m — концентрация субстрата, при которой активность фермента (или агониста, ингибирование которого исследуется) равна 50 % от максимальной.

Файлы с 3D структурой белка и лигандов

Программы берут на вход трехмерные структуры молекул, например .pdb и .pdbqt

Трехмерную структуру белка рицина для своей работы я скачал с Protein data bank.

Структуры лигандов можно создать с помощью различных конструкторов (например: CORINA). Список таких программ можно найти тут.

Но я решил использовать уже существующие лекарственные вещества, для которых известны различные фармакокинетические особенности. Производные гетероцикла птеридина я скачал с Drugbank.

Модификация белка

Модификация необходима для лучшего моделирования взаимодействия.

Для этого мы добавляем полярные молекулы водорода в структуру белка. Для этого запускаем MGL Tools и выполняем следующие действия:

File > Read molecule > 'some_protein.pdb' > Open

Edit > Hydrogens > Add > Polar only > OK

Grid > Macromolecule > Choose > 'some_protein' > Select molecule > OK > Save

Теперь у нас есть файл макромолекулы для последующего докинга.

Определение "коробки" докинга

Под "коробкой" подразумевается то пространство, где программа будет моделировать взаимодействие лиганда и белка. Важно отметить, что внутри этой "коробки" лиганд будет всячески перемещаться и вращаться, для определения лучшей энергии связывания. Поэтому с ростом объемов "коробки" многократно возрастает и время работы.

На этом этапе важно обработать литературу и узнать где именно находится у данного белка активный центр. В моем случае, каталитический центр субъединицы А молекулы рицина составляют остатки тирозина в позициях 80 и 123, глутаминовой к-ты – 177, аргинина – 180. Однако остатки таких аминокислот как аспарагин – 75, треонин – 77, валин – 81, аспарагин – 122, изолейцин – 172, глутамин – 173, серин – 176, глутаминовая к-та – 208, триптофан – 211, и валин – 256, находящихся в непосредственной близости с каталитическим сайтом, могут участвовать в образовании связи с низкомолекулярным веществом.

Чтобы визуализировать эту информацию, нажимаем на маленький треугольник напротив названия нашего белка. Открылась структура макромолекулы - это субъединицы 'A' и 'B'. То же самое проделываю для субъединицы 'A' и вижу список аминокислотных остатков. Если нажать на квадратик напротив аминокислоты, то все ее атомы выделяются в общей структуре белка. Проделав это со всеми аминокислотами активного центра можно увидеть активный центр, который необходимо заблокировать.

Молекула белка уже открыта в MGL Tools и мы выполняем команды:

Grid > Grid box

В открывшемся окне выбираем размеры "коробки" и ее центр, посредством скролла каждого колесика.
Записываем полученные параметры, а именно значения: x-dimension, y-dimension, z-dimension, x-center, y-center, z-center. Важно записать не только цифры, но и то, что они значат. Закрываем окно.

Модификация лигандов

При модификации лиганда мы добавляем возможность внутреннего вращения молекулы вокруг связей во время моделирования.

Чтобы не мешал открытый ранее белок, можем скрыть его или перезапустить MGL Tools. Выполняем действия:

Ligand > Input > Open > 'some_ligand.pdb' > OK

Ligand > Torsion tree > Choose Torsions >

Мы видим связи вокруг которых возможно вращение. Зеленым цветом обозначены связи вокруг которых мы разрешаем вращение, а фиолетовым - связи, вокруг которых вращения не будет при последующем докинге. Кликая по связям можно менять их цвета.

> Done

Ligand > Output > Save as .PDBQT > 'some_ligand' > Save

Файл лиганда готов. Закрываем MGL Tools. Данный этап нужно пройти столько раз, сколько у вас есть лигандов. Я искать возможности автоматизации этого процесса, но так и не понял как это сделать.

Создание конфигурационного файла

Этот этап не обязателен, но так как Autodock Vina принимает на вход очень много параметром, то имеет смысл записать некоторые в файл и его уже дать на вход программе.

В моем случае в файл conf.txt я записал следующее: 

center_x = 24 
center_y = 66
center_z = 52
size_x = 24 
size_y = 24 
size_z = 24 
num_modes = 3

Сюда же пише ранее определенные параметры "коробки" докинга. Параметр "num_modes" обозначает сколько лучших вариантов программа запишет в выходной файл. По умолчанию этот параметр равен 100.

Запуск Autodock Vina

Как я уже говорил, Autodock Vina - это программа, запускающаяся с командной строки. Данный этап будет немного отличаться для разных операционных систем. Пока рассмотрим вариант с Windows.

Для удобства я создал папку "biomodeling" в корне диска D в которую положил файлы белка, лигандов и папку с программой Vina.

Открывает командную строку (терминал):

Пуск > Выполнить > cmd > OK

Переходим в нужную директорию. В командной строке пишем:

cd D:\biomodeling

Чтобы узнать какие параметры программы, вызываем справку:

"Vina\vina.exe" --help

 Ну и собственно запуск:

"Vina\vina.exe" --receptor some_protein.pdbqt --ligand some_ligand.pdbqt --config conf.txt --all some_ligand_results.pdbqt --log log.txt

Как было сказано ранее, некоторые параметры можно заранее записать в конфигурационный файл. Обязательно нужно указать название log-файла и файла в котором сохранятся результаты моделирования (параметр --all).

Автоматизация процесса

У меня было много лигандов и я написал сценарий для командной строки. Создает текстовый документ и переименовываем в docking.bat

cd D:\Biomodeling\Ricin
rem Это комментарий
for /D %%i in (DB08448, DB02692, DB02031, DB08406, DB04047, DB02911, DB04262, DB03332, DB03256, DB02718, DB02800, DB04375, DB04789, DB02214, DB02119, DB03197, DB03918, DB04726, DB04610, DB02278, DB04400, DB03271, DB04425, DB04345, DB03886, DB03883, DB02015, DB07765, DB07689, DB02385, DB02164, DB03830, DB04357, DB03592, DB04196, DB02562, DB02067) do (echo "Докинг протеина с лигандом" >> log.txt | echo %%i >> log.txt | "Vina\vina.exe" --config conf.txt  --ligand %%i.pdbqt --out %%iout.pdbqt --log >> log.txt)
echo "Конец докинга!" > log.txt

Двойным кликом запускаем этот файл и идем спать :)

Послесловие

Все инструкции, которые описаны здесь вы можете найти в официальном видеотуториале Vina.

P.S.

Если у вас возникли сложности пишите на kazanzhy@mail.ua или dkazanzhy@gmail.com