генетический код (соответствие РНК и аминокислот)

> Единственное, что приходит в голову - это ОЧЕНЬ МНОГО вложенных циклов for. Комбинаторный алгоритм. Перебрать все возможные комбинации. Но я это даже не могу использовать - потому что заранее мне даже неизвестен уровень вложенности - он зависит от исходных данных.

Что мешает составить простенький рекурсивный алгоритм с параметром определяющим глубину вложенности? 6 - смешная глубина рекурсии же.

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

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

На ночь глядя я что-то с трудом представляю задачу) Алгоритм более-менее формализованный есть? А то разбираться в биологии как-то не особо хочется, а вот порешать задачку можно.

Тут далеко не 6 будет глубиной... а 6*4*6*3*6*2*1*1*6*... и далее в случайном порядке. числа от 1 до 6 (не считая 5)... как-то так.

И, повторюсь, я заранее не знаю, какой именно будет эта глубина. %)

И как рекурсивный алгоритм сделать - до меня что-то не доходит никак.

Я не программист, но по моему тут проще на scheme'е написать, не?

Там биологии вообще, считайте, нет. Объясню проще.

Есть алфавит из 4 букв. Есть ещё один алфавит из 20 букв.

Каждые 3 буквы из первого алфавита (последовательность XYZ) ОДНОЗНАЧНО соответствует ОДНОЙ букве (из 20) из второго алфавита. Это очень легко. И это я уже сделал...

а вот наоборот - сложнее. Каждая одна буква из второго алфавита соответствует ТРЁМ буквам. И уже не однозначно определёно - каким... тут может быть от одной до шести разных комбинаций. Либо то, либо то, либо другое. и надо всё перебрать...

а последовательности могут быть длинными... очень длинными.

То есть, например, если во втором случае даны всего две буквы. пусть A и N. результатом должны быть все комбинации возможные, где первые 4 элемента на выбор GCU, GCC, GCA, GCG, а вторые два AAU, AAC.

Например, GCUAAU или GCUAAC, или GCAAAU. Их надо перебрать все.

Нюанс в том, что может быть букв не две, а, например, две тысячи или два миллиона... Наверное, через рекурсию как-то... но я не знаю, как её сюда приплести.

Мне в принципе пофик на чём... нюанс разве в том, что с scheme я вообще не знаком, и вообще все функциональные языки для меня - тёмный лес... мне бы проще на c/c++, или чём-то подобном.

> а последовательности могут быть длинными... очень длинными.

Порядок какой, в грубой оценке? Тясячи, десятки тысяч, миллионы?

Единственное, что приходит в голову - это ОЧЕНЬ МНОГО вложенных циклов for.

Вот. Я не первый раз встречаю эту фразу. И всегда она 100% указывает на быдлокодера.

Пичалька.

Начинай становиться человеком отсюда: http://ru.wikipedia.org/wiki/Динамическое_программирование

Ээээ... Если я правильно понял эту математику, то при условии, что мы имеем тысячу букв, каждой из которых соответствует допустим две трёхбуквенные последовательности, то мы имеем 2^1000 вариантов.

Эта задача точно решаема за обозримое время? Или я туплю?

Возможно, что и нет... Комбинаций очень много... Ну наверное для тысячи букв может и не понадобится... так мол и так, скажу, что нерешаема. Но алгоритм хотя бы... чтобы для малых порядков (десятков-сотен) работал, мне бы не помешал. %(

Насколько мне известно, кроме A, C, G, T, есть ещё дополнительные символы которые обозначают сразу несколько возможных вариантов нуклеотидов. Например W = (A | T). Почему бы тебе не хранить их так, и при вычислении учитывать это? Кстати, очень удобно было бы использовать битовые поля для этого.

самый низ: http://www.genomatix.de/online_help/help/sequence_formats.html

текс... если я правильно понял, тебе из поледовательности Ala/A, Arg/R,... нужно получить все возможные последовательности UUU, UUC,...

Если это так, то в лоб можно решить примерно так: http://pastebin.com/qABSDJw6

*сразу уточняю, питон не знаю, написал этот код на нём, т.к. сегодня решил поковырять его

Идея следующаяя:

Триплеты и аминокислоты кодируем целыми числами(так быстрее будет+памяти жрать мньше будет) и пихаем в мапу(у меня это table1). Далее на вход функции подаём посл. кодов аминокислот.

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

Далее делаем нужное кол-во проходов(тут сделал первое, что пришло в голову, переполнение обеспеченно на реальных данных) каждый раз увеличивая один из счётчиков на 1. Плюс после прохода смещаем `смещаемый элемент`. Все смещения счётчиков и счётчика смещаемого счётчика циклические по длинам соотв. списков.

Код работает, но осбой скорости не ожидается(да её и не будет, т.е. кол-во перебираемых вариантов оч. велико).

То есть, например, если во втором случае даны всего две буквы. пусть A и N. результатом должны быть все комбинации возможные, где первые 4 элемента на выбор GCU, GCC, GCA, GCG, а вторые два AAU, AAC.

Например, GCUAAU или GCUAAC, или GCAAAU. Их надо перебрать все.

Нюанс в том, что может быть букв не две, а, например, две тысячи или два миллиона...

ну а комбинации находи всегда для двух, а дальше пходи комбинацию полученных своих цепочек( GCUAAU или GCUAAC, или GCAAAU...) со следующим элементом, и т.д.

Все дело в том, что работать с таким гигантским списком почти нереально, правильнее просто проиндексировать его по значению выборов конкретных последовательностей РНК для многозначных аминокислот. И просто знать, как по индексу восстановить последовательность РНК.

Вообще наверняка должен быть уже софт для такой задачи.

Онлайн-сервисов дофига http://www.biophp.org/minitools/protein_to_dna/demo.php

> ну а комбинации находи всегда для двух, а дальше пходи комбинацию полученных своих цепочек( GCUAAU или GCUAAC, или GCAAAU...) со следующим элементом, и т.д.

Оперативка в таком варианте будет быстро и безвозвратно загибаться))

Подождите!!! А книгу Дэна Гасфилда «Строки, деревья, и последовательности в алгоритмах» вы читали? Там есть много приложений к биологии, возможно и ваша задача решается.

тогда можно так.

цепочку аминокислот представить как позиционную систему счисления с переменным основанием, где количество триплетов РНК соответствующих аминокислоте, есть основание этого разряда числа.

Задача сводится к переводу всех десятичных значений от 0 до n в полученную систему счисления, где n - количество всех комбинаций.

Таким образом ты и память не будешь забивать, сможешь переводить длиные последовательности

Ты не поверишь, я чуть выше привёл код на питоне делающий это;)

ну у тебя как то там все сложно.

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

Уф, давай код, а то из твоего описания я ничерта не понял.

по мне достаточно лишь заминить аминокислоты числом - основанием разрядов,

Триплеты для каждой аминокислоты различны - это раз. Два, есть совпадающий основания. Как будешь определять конкретный тип аминокислоты, чтобы вытащить триплет? В общем, давай код, так будет проще.

Как будешь определять конкретный тип аминокислоты, чтобы вытащить триплет?

дак по исходной последовательности аминокислот. Код сильно долго от меня ждать, ибо в development зашел лишь из-за заголовка. Лучше графически изображу.

http://s1.ipicture.ru/uploads/20110529/p4gsYn47.png

числа и значения брал выдуманные: допустим аминокислоте М соответствует пять триплетов. произведение всех оснований дает 240 комбинаций. Для числа из отрезка 0...240 для некотгрого i = 145, число в позиции соответствующей М = 4. То есть соответствует четвертому триплету для данной аминокислоты из возможных от 0 до 4

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

> Триплеты и аминокислоты кодируем целыми числами(так быстрее будет+памяти жрать мньше будет) и пихаем в мапу(у меня это table1). Далее на вход функции подаём посл. кодов аминокислот.

Да по идее разницы быть не должно... char это тоже по сути целые числа... разве нет? если не на питоне, а на сях... ну можно и на питоне...

> Онлайн-сервисов дофига http://www.biophp.org/minitools/protein_to_dna/demo.php

Ох... а вот это очень интересно =) может, я на этом и остановлюсь, мне хватит? :) посмотрю, в общем... может мне и не надо ничего своего писать... от меня так и не требовали... главное, чтобы работало, если есть готовая программа, даже в плюс наверное :)

char - это целое число в диапазоне [-127, 127] или [0, 255], т.е. это один байт памяти. Ну на сях это будет больше кода и больше возни с ним, а так, разницы не будет.

по той ссылке он не очень правильно работает... или точнее, я не понимаю, как он работает.

Например, для A он выводит GCN, то есть третья буква N - это любая из возможных... но все он их не перечисляет =)

там только для нескольких частных случаев

А зачем вообще может быть нужно перебирать _все_ варианты рнк?

Затрудняюсь пока ответить на этот вопрос... спрошу и узнаю =)

Я думаю тут поможет ООП. Что если запаковать процесс декодирования и его результат в объект, и при встрече неоднозначной последовательности делать копию.

звучит очень туманно.

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

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

Были предложены способы как перевести часть сложности по памяти в сложность по времени, и наоборот, вроде. Но сам результат, который надо получить, гаргантюанский.

Кстати, помимо правильной книги Гасфилда, которую тут уже рекомендовали по этой теме, порекомендую еще книгу Искусственный интеллект. Современный подход. Там есть отдельные главы про задачи поиска, и к чему в конце-концов сводятся алгоритмы их решения.

О динамическом программировании посмотрите у Кормена.

Кроме того, попробуйте посмотреть на prolog. Он конечно не поможет получить решение быстрее, но зато поможет взглянуть на задачу с другой стороны, с которой будет понятнее как задачу решать.

А вот еще идея - ленивые вычисления. Скорее всего, результат о котором вы упоминали - промежуточный. Далее с ним будут производиться какие-нибудь дополнительные действия, правильно? Имейте ввиду.

Короче говоря, можно пошире взглянуть на задачу.

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

ясно... надо много читать.

насчёт того, результат промежуточный или окончательный - точно сказать не могу, ну думаю, что промежуточный. Спросил сегодня - результат нужно получить такого вида: один текстовый файл (типа таблицы), в нём много-много столбцов. каждый столбец - это одна возможная цепочка ДНК (РНК). Например:

U G C A .......

U C G A .......

U U U C .......

То есть UUU, GCU и т.п. - это триплеты возможные (подбирал случайно).

Понятно, что их более чем до хрена и при увеличении длины цепочки аминокислот растёт экспоненциально - но в ресурсах я особо сильно не ограничен. можно хоть кластер задействовать... и времени можно считать есть часы-дни-недели... думаю, тут алгоритм особо оптимизировать и не получится, считать всё равно только «в лоб». пока буду думать над реализацией...

Я в функциональных языках вообще 0 пока что - но вы говорите, для этой задачи что-то подобное и нужно выбирать, да? :)

Да любой язык подойдет для решения этой задачи.

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

Кроме того, для различных взглядов на условие задачи будут свои идиомы для решения. Например, при взгляде на задачу как на поиск в пространстве состояний, решением будет иметь вид одного из алгоритмов поиска (см. выше ссылку на книгу), при взгляде на задачу как на задачу оптимизации, решение будет записано с использованием идей динамического программирования.

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

man взаимная однозначность.

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

про деревья мне даже в голову не приходило...

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

надо подумать... может, попробую =)

Ну вот, собственно, один из вариантов поиска. Описан поиск очень хорошо, например, в книге Исусственный Интеллект. Современный подход. (AIMA).

Почему именно в ней, а не в какой-нибудь книге, посвященной алгоритмам? Потому что там различные варианты поиска в пространстве состояний рассматриваются с общих позиций.

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

Кроме того, если вам хочется самостоятельно не кодировать обход дерева (что конечно же тривиально, но немного затемняет суть происходящего), то посмотрите на prolog. А вот еще взгляните - вроде в SICP приводится пример неоднозначного интерпретатора amb.

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

А книжка-то большая, почти 1500 страниц %( прочитал бы всю... жаль, живём только один раз.

я так понимаю, то, что мне нужно, описано в главе «информированный поиск и исследование пространства состояний»?

Кстати. Самое главное спросить забыл. А предложенный алгоритм поиска может (в теории) работать параллельно на нескольких компьютерах? В случае, если объём данных действительно большой...

Это может быть критично... как по времени, так и по памяти.

Если требуется распараллеливание именно обхода дерева - то тут существует множество алгоритмов, по этому поводу есть даже соответствующая литература.
Например, http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mm&paperid=361&opti... или www.ict.edu.ru/vconf/files/11953.pdf.

Понятно... над этим потом отдельно подумаю.

Кстати, алгоритм перебора с использованием дерева описывается (оказывается) в книжке «Окулов - программирование в алгоритмах», которая у меня давно уже дома лежит в бумажном виде, пылится (купил, когда был ещё школоло). :) Суть я понял. Правда, возможно, мне даже дерева строить и не надо... но мне в любом случае надо построить рекурсивную процедеру его обхода... или построения. В общем, я над этим подумаю.

Ещё кое-что меня натолкнуло на мысли. Если предположить, что, к примеру, цепочка аминокислот длины больше 30 (например, 40 или 50). И каждая из аминокислот в среднем пускай соответствует 2-м триплетам. Тогда для описания только количества возможных комбинаций мне необходимо число 2^40. А тип long int позволяет только 2^32 чисел описывать...

В идеале мне бы надо предусмотреть для любой возможной длины... То есть задействовать целые числа произвольной точностью (разумеется, с ущербом производительности, ну да и пусть). Что-то слышал про gmp - это то, что мне нужно, да?

Я таки разобрался, как сделать требуемый от меня алгоритм без использования деревьев и рекурсии. Перевёл (почти) рекурсивный алгоритм обхода в итеративный. получается (пока в теории) три вложенных цикла.

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

А принцип всё тот же... Вообще говоря, тоже дерево обхожу. просто необязательно для этого создавать в памяти его структуру.

В общем, результат такой - всё у меня получилось. Если кому вдруг интересно - могу выложить готовый код... который всё делает хорошо. И не использует ни деревьев, ни рекурсии. ну разве что «на кончике пера».

Жрёт памяти немерено... на цепочке из 10-ти элементов работает ещё сносно - а вот если больше - начинает тупить от недостатка памяти.

Можно это оптимизировать... сбрасывая буфер на диск, и высвобождая оперативную память - в принципе это реально. Реально её необходимый объём меньше...