Доказательство хиральности

[madschumacher]

Добрый вечер Всем!

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

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

Как говорится, thank You 4 Your attention!

[amge]

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

Итак, два случая. Первый - когда у молекул согласованная нумерация атомов. Тогда помещаем молекулы в центры масс и вращаем их до минимального RMS между ними. Если получаем близкий к нулю RMS - молекулы совпадают, в противном случае - (применительно к Вашей задаче) оптические изомеры. У меня этот алгоритм реализован в программе align. См.также Calculate RMSD from two XYZ files. Данный алгоритм весьма быстр. Второй случай - нумерация атомов несогласованная. Тогда вычисляем тензоры инерции молекул и ориентируем их (молекулы) по осям эллипсоида инерции, опять вычисляем RMS. Это реализовано в программе tenzor. Работает не так быстро. Оба подхода совмещены в программе conformers, пользовать ее можно через скриптик типа

Код: Выделить всё

#!/bin/bash

cat $* > TEMP.xyz
conformers -no_mopac TEMP.xyz |grep ', RMS '
rm TEMP.*.xyz

[madschumacher]

Спасибо большое! У меня как раз нумерация совпадающая.

А можно вместо вращения найти матрицу ортогонального преобразования из системы линейных уравнений? Это же вроде по сути одно и то же?

[uchebnik fiziki]

Второй случай - нумерация атомов несогласованная. Тогда вычисляем тензоры инерции молекул и ориентируем их (молекулы) по осям эллипсоида инерции, опять вычисляем RMS. Это реализовано в программе tenzor. Работает не так быстро.

Зачем такие сложности, если можно сначала канонизировать нумерацию? В случае вращения бензольного кольца может, кажется, не сработать, но задачу вроде упростит.

[amge]

А можно вместо вращения найти матрицу ортогонального преобразования из системы линейных уравнений? Это же вроде по сути одно и то же?

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

[amge]

Зачем такие сложности, если можно сначала канонизировать нумерацию? В случае вращения бензольного кольца может, кажется, не сработать, но задачу вроде упростит.

Пробовал я канонизацию. Совсем не понравилось. Проблема в том, что слишком много случаев, когда атомы получаются топологически эквивалентными и нумеруются "от фонаря". Кроме уже упомянутого Вами бензольного кольца и других симметричных циклов это еще, например, одинаковые геминальные группы (напр., метилы в изопропаноле). А мне же еще и водороды учитывать: куча СН2 и СН3 с эквивалентными протонами. Каждый такой случай учывать - замаешься.

[VTur]

Раньше это решалось и так. Приводите молекулы к главным центральным осям. Разбиваете декартово пространство плоскостями, проходящими через оси, на 8 частей или меньше 4. Если число атомов или их массы или еще какой признак в каждой осьмушке совпадает - это одно и тоже, если нет - оптические изомеры. Это очень быстро. Хотя можно и вращать вокруг любой из выбранных главных центральных осей до совпадения или несовпадения атомов.

[madschumacher]

Спасибо за идею, Amge!
Реализовал поиск матрицы преобразования координат (не вращением, а через МНК по известным координата) и вроде все работает.
Если det(A)=1, то конформеры одинаковы, а если det(A)=-1, то они не сводимы друг к другу, где A - матрица преобразования.

[Jokermaniak]

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

Это взгляд бывшего программиста, кодившего в студенческие годы в области, далекой от химии.

[madschumacher]

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

[ Post made via Android ]

[Jokermaniak]

Если хотите, можете присоединиться к ваянию сего весьма узконаправленоого быдлокода, то буду очень рад!

Эх, не травите душу Я в завязке уже четыре года, больше не программирую...

...две молекулы, данные в виде Декартовых координат, для которых установлено, что все пары межатомных расстояний в них равны

А как реализована компарация? Я так понимаю эта функция с точностью до поворота идентичность возвращает?

[madschumacher]

Там по МНК ищется матрица ортогонального преобразования. Реально - решается система 6ти линейных уравнений, где неизвестные - элементы матрицы и потом проверяется значение определителя полученной матрицы.

[Jokermaniak]

Реально - решается система 6ти линейных уравнений, где неизвестные - элементы матрицы и потом проверяется значение определителя полученной матрицы.

То есть быстродействие О(1), если я Вас правильно понял? Дык тут уже быстрее не сделаешь...

[madschumacher]

Насчет быстродействия я бы не стал говорить, поскольку там в коде есть куски куски с производительностью O(n!). И он вообще и память и ресурсы жрет. Для малых молекул ничего, терпимо, но для большего надо вообще весь алгоритм и структуру переделывать. Но это Not my problem)

[Jokermaniak]

Стоп, как быстродействие решения системы из 6 (константа) скалярных уравнений может оцениваться чем-то, отличным от константы? Видимо, кроме решения этой системы есть ещё работы в задаче? Откуда всплывает O(n!)? Вы уж простите, мне сложно воспринимать такие фразы, как "по МНК ищется матрица ортогонального преобразования" - матаппарат оргквантов я знал только на четвертом курсе, и уже почти всё забыл...

И ещё - задача определения идентичности с точностью до операций симметрии, я так понимаю, решена отдельно. Если она неприкосновенна, и задача просто допилить к ней хендл энантиомеров - ИМХО нет смысла дергаться. Но вот алгоритм, который с нуля, с картезиан, вернет идентичность с точностью до поворота, через хэши или метрики графов скорее всего будет быстрее. Особенно для больших молекул.

[madschumacher]

Программа конкретно эта завязана на Декартовы координаты. N! вылезает из генерирования числа перестановок ядер, задача о хиральности - всего лишь малая часть алгоритма, являющееся одним из условий принятия/отвержения. Наверняка теория графов позволила бы снизить ресурсосжираемость программы, но это пока не моё дело, поскольку объектов таких нет, и те, кому это интересно, навряд ли будут юзать этот конкретный код.

Там проверяется сначала условие существования подобного преобразования(что жрёт существенно больше памяти и времени), а уж потом ищется это преобр.

Уравнение мнк:
Sum_i(r'_i-Ar_i)^2 -> min, где r, r' - начальные и конечные координаты i-го атома, А - матрица преобразования. Квантов тут нет, просто линейная алгебра. Ещё раз спасибо Amge за идею!

[ Post made via Android ]

[uchebnik fiziki]

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

Решением подобных задач в общем виде занимался и, кажется, до сих пор занимается С. С. Трач. Посмотрите его работы (он пишется и как Tratch, и как Trach). Но там в первую очередь очень суровая теория графов.