Голосовой поиск

Голосовой поиск

Разработчик(и)	Ян Холмс ( Калифорнийский университет в Беркли )
Стабильная версия	1
Написано в	Дарт
Операционная система	UNIX , Linux , Mac , Cygwin в Windows XP
Тип	Инструмент биоинформатики
Лицензия	Открытый исходный код
Веб-сайт	Домашняя страница Стемлока

В биоинформатике , Stemloc — это программное обеспечение с открытым исходным кодом для выравнивания множественных последовательностей РНК и прогнозирования структуры РНК на основе вероятностных моделей структуры РНК известных как парные стохастические контекстно-свободные грамматики (также вероятностные контекстно-свободные грамматики). Stemloc пытается одновременно предсказать и выровнять структуру последовательностей РНК с меньшими временными и пространственными затратами по сравнению с предыдущими методами с той же целью. В результате программное обеспечение реализует ограниченные версии алгоритма Санкоффа, вводя ограничения как по сворачиванию, так и по выравниванию, что снижает использование процессора и памяти и позволяет анализировать более крупные последовательности РНК на обычном оборудовании. Stemloc был написан в 2004 году Яном Холмсом.

Stemloc можно загрузить как часть программного пакета DART . Он принимает входные файлы в формате FASTA или Stockholm .

Терминология

• Складывание : сворачивание РНК — это процесс, посредством которого молекула РНК приобретает вторичную структуру посредством внутримолекулярных взаимодействий.
• Конверт сгиба : набор возможных складок, которые будут учитываться в алгоритме.
• Конверт выравнивания : набор возможных выравниваний, которые будут учитываться в алгоритме.

Фон

Ранее разработанный Дэвидом Санкоффом в 1985 году алгоритм использует динамическое программирование для одновременного выравнивания и прогнозирования нескольких структур РНК. Алгоритм Санкоффа использует время и пространство в большой записи O. $O(L^{3N})$ и $O(L^{2N})$соответственно для $N$ последовательности длины $L$. Это очень дорого, и поэтому является мотивацией для создания более совершенных инструментов анализа РНК, таких как Stemloc. Первоначальная цель Stemloc состояла в том, чтобы сократить временные и пространственные затраты на одновременное выравнивание и предсказание структуры двух последовательностей РНК за счет использования схемы оценки стохастической контекстно-свободной грамматики (SCFG) и реализации ограниченных версий алгоритма Санкоффа.

Stemloc использует конверты выравнивания и конверты складки, чтобы одновременно ограничить как выравнивание, так и вторичные структуры сравниваемых последовательностей. Складчатые конверты можно использовать для «обрезания» поиска по вторичным структурам и определения подпоследовательностей двух последовательностей РНК, которые можно учитывать в алгоритме. Например, включение или исключение определенных пар оснований, связанных азотом. Конверты выравнивания можно использовать для «обрезки» поиска по выравниваниям и определения возможных «точек пересечения» в выравнивании двух последовательностей. Например, включение или исключение конкретных гомологий на уровне остатков. Конверты сгиба предварительно рассчитываются для каждой последовательности индивидуально, а конверты выравнивания предварительно рассчитываются путем сравнения двух последовательностей при игнорировании вторичных структур. как глобальное, так и локальное выравнивание Поддерживается .

Вход

Ввод в Stemloc может быть в формате FASTA или Stockholm (описание каждого из них см. выше). Пример ввода показан ниже:

stemloc --local dynalign.trna

Команда «--local» анализирует файл в режиме локального выравнивания. Использование «--global» будет использовать режим глобального выравнивания.

Выход

Этот вывод имеет стокгольмский формат . Он показывает имена последовательностей, координаты совпадений, выравнивание, согласованную первичную последовательность, вторичную структуру каждой последовательности, согласованную вторичную структуру и оценку логарифмических шансов выравнивания в битах. Линия «//» используется для разделения выравниваний или обозначения конца файла. Пример вывода показан ниже:

# STOCKHOLM 1.0
#=GR RD0260/26-67 SS ..<<<<<.......>>>>>.....(<<<<.......>>>>).
RD0260/26-67			UACUCCCCUGUCACGGGAGAGAAUGUGGGUUCAAAUCCCAUC
#=GC PS_cons			UAC..CCCUGUCACGG..G.GA..G.GGGUUC.AAUCCC..C
RD0500/26-66			UACGACCCUGUCACGGUCGUGA-CGCGGGUUCgAAUCCCGCC
#=GR RD0500/26-66 SS ..<<<<<.......>>>>>...-.<<<<<.......>>>>>.
#=GC SS_cons			..<<<<<.......>>>>>.....<<<<<.......>>>>>.
#=GF SC				  31.872
//

Процесс

Stemloc в значительной степени полагается на стохастические контекстно-свободные грамматики, которые можно рассматривать как схему оценки алгоритма. Поскольку алгоритм Санкоффа учитывает все возможные складки и все возможные выравнивания, он достаточно точен и тщательн, но для получения каких-либо результатов или вывода требуется измеримое количество времени. Чтобы улучшить эту ситуацию, Stemloc позволяет пользователю ограничить общее количество учитываемых складок и выравниваний. Более конкретно, каждая последовательность может быть предварительно сложена индивидуально в $O(L^{3})$ времени и заранее согласованы, игнорируя вторичную структуру в $O(L^{2})$ время. Например, использование приведенной ниже команды «-fast» будет учитывать только 100 лучших структур РНК, а не анализировать все возможные складки. Использование команды «-log DOTPLOT» выведет визуальное представление конвертов сгиба и выравнивания.

stemloc nanos-tiny.rna -fast -log DOTPLOT

Ограничение конвертов

Основная идея Stemloc — возможность установить порог количества складок и выравниваний, которые выбираются для создания конвертов. Это можно сделать с помощью опций «-nf» и «-na», которые задают количество учитываемых складок и выравниваний. (Использование -1 ограничивает количество выбранных складок и выравниваний, поэтому использование -1 для обоих параметров запустит алгоритм Санкоффа для входного набора данных.

stemloc nanos-tiny.rna -nf -1 -na -1

Обучение параметров

Еще одной особенностью Stemloc является его способность параметризовать вероятностные модели, такие как стохастические контекстно-свободные грамматики, на основе данных. Stemloc использует алгоритм Inside-Outside и стохастические контекстно-свободные грамматики, чтобы максимизировать вероятность обучающего набора. Это полезно, поскольку параметры по умолчанию для Stemloc были обучены на выборке парных выравниваний с идентичностью последовательностей от 30% до 40% из Rfam (база данных) версии 5.0. Однако эти параметры не всегда эффективны, поэтому возможность обучения параметров пользователем может быть полезной.

На практике

С тех пор Stemloc использовался в различных исследовательских публикациях по анализу структуры РНК. Особенно это касается изучения оптимального выравнивания множественных последовательностей.

Ссылки

• Холмс И. (2005) Ускоренный вероятностный вывод об эволюции структуры РНК . БМК Биоинформатика. 2005, 24 марта;6:73.
• Санкофф Д. (1985) Одновременное решение проблем сворачивания, выравнивания и протопоследовательности РНК . SIAM Journal по прикладной математике. Октябрь 1985 г.; 45:5. Санкофф Д. (1985) Одновременное решение проблем сворачивания, выравнивания и протопоследовательности РНК. SIAM Journal по прикладной математике. Октябрь 1985 г.; 45:5.

Внешние ссылки

• Stemloc Домашняя страница и руководство