Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
(DEF (FACTORIAL(N) если N = 0, вернуть 1, иначе вернуть
(COND произведение N и факториала числа
((ZEROP N) 1) N - 1
(PROD (N (FACTORIAL(SUBl N)))))))
Мы часто пользуемся рекурсивной функцией, называемой SUBSET, для
определения, все ли атомы, указанные в списке фрагментов, имеются в
молекуле. В языке лисп эта функция настолько компактна и так хорошо
показывает характер рекурсии, что мы воспроизведем ее здесь:
(DEF (SUBSET(FRAG MOL)
(COND
((NULL FRAG) T)
((MEMBER (CAR FRAG) MOL) (SUBSET (CDR FRAG) MOL)))))
В приведенном виде эта программа нефункциональна; для упрощения здесь
были опущены некоторые особенности. Предполагается, что как MOL, так и
FRAG - списки атомов (LAT), и предполагается, что ни один атом не
появляется более одного раза в списках MOL или FRAG. Выражение CDR FRAG -
список атомов, полученный в результате удаления первого атома из списка
FRAG. Любой список составлен из его CAR-части (первый элемент списка) и
* Заключенным между двумя ограничителями языка лисп - Прим перев
Программа на языке лисп
533
его CDR-части (остальные элементы). Исторически случайные наименования
CAR и CDR обозначают регистры в устаревшей в настоящее время машине.
Последней особенностью лисп, которая необходима для понимания нашего
представления фрагментов, является присвоение "свойства". Рассмотрим
лисп-атом GEORGE. Мы можем связать с атомом GEORGE любое число атрибутов.
Например, атому GEORGE можно присвоить свойство ADDRESS следующим
образом:
PUTPROP (GEORGE, ADDRESS, ATHENS)
Мы можем извлечь ADDRESS из списка свойств атома GEORGE с помощью функции
GETPROP:
GETPROP (GEORGE, ADDRESS)
Здесь ATHENS - значение свойства ADDRESS атома GEORGE.
3. ПРЕДСТАВЛЕНИЕ МОЛЕКУЛ С ПОМОЩЬЮ ЯЗЫКА ЛИСП
Молекула в нашей программе на языке лисп представляется списком атомов.
Имеется схема нумерации, присваивающая однозначно метку каждому атому в
этом первичном списке. Такие атомы имеют множество свойств. Каждый атом
имеет общее для данного типа атомов имя в качестве лисп-свойства.
Например, CARBON - значение свойства NAME для С9. Таким путем мы можем
идентифицировать каждый атом С, признавая в то же время его сходство с
другими атомами С. Наиболее важным свойством (PROPERTY) атома является
список его соседей (NEIGHBOR). Это свойство содержит всю необходимую нам
топологическую информацию. Оно сообщает, как только нам потребуется
знать, что С9 связан непосредственно, например, с атомами (С8 СЮ Н12
Н13). Свойство NEIGHBOR аналогично матрице смежности, известной из теории
графов.
Хотя структура данных в нашей программе довольно проста, необходимо
ввести сравнительно много данных, описывающих общие химические фрагменты.
Для облегчения этой задачи мы адаптировали стандартную подпрограмму
обработки графического отображения для передачи схематического
изображения структурной формулы машине APPLE(TM), которая будет
передавать информацию ЭВМ CYBER 720 Университета шт. Виргиния. Основной
процесс обработки данных осуществляется с помощью "локальной" версии лисп
Университета шт. Техас (версия 5.1).
534
К. Триндл, Р. Гиван
4. НЕФОРМАЛЬНЫЙ АЛГОРИТМ РАСПОЗНАВАНИЯ
ФРАГМЕНТОВ
Сложная молекула может рассматриваться как ряд известных фрагментов,
связанных между собой некоторыми простыми способами. Проблема определения
одного из (вообще говоря, многих) способов разбиения молекулы на
фрагменты включает некоторые классические проблемы информатики.
Распознавание образов необходимо для того, чтобы удостовериться в том,
что фрагмент действительно содержится в молекуле; должна быть разработана
оптимальная стратегия поиска, так чтобы выбрать наиболее целесообразное
разбиение молекулы на фрагменты среди очень большого числа возможных. Эта
проблема известна как "задача о ранце", поскольку она сходна с задачей
нахождения наилучшего способа упаковки вещей в мешок ограниченных
размеров. Мы можем показать, что оптимальное представление фрагментов
содержит большие фрагменты, в значительной степени перекрывающиеся.
Критерий оптимальности представления выделяет долю всех расстояний в
молекуле, имеющихся во фрагментах. Вторичным критерием является то, что в
представление включается незначительное число фрагментов. Для простоты мы
начнем с неперекрывающихся фрагментов; молекула с А/ атомами будет
разбиваться на К фрагментов со средним числом М/К атомов в каждом из них.
Фрагменты несут информацию о каждом внутрифрагментном расстоянии, число
которых (М/К)(М/К - 1)/2. Полное число определенных расстояний равно
М(М/К - 1)/2, тогда как необходимо М(М - 1)/2 расстояний. Доля известных
расстояний равна (М/К - 1 )/(А/ - 1) или, в пределе при М - оо, \/К.
Очевидно, что К должно быть малым, в идеале 1! (см. рис, 1).
Если перекрывание фрагментов не допускается (т. е. каждый атом в молекуле
отнесен только к одному фрагменту), то межфраг-ментные расстояния никогда
не будут определяться. Если фрагменты могут перекрываться, то возможно,
что наибольшие расстояния могут быть представлены как свойства
