мерцание

мерцание
Разработчик(и)	Стивен Зальцберг и Артур Делчер
Стабильная версия	3.02 / 9 мая 2006 г.
Доступно в	С++
Тип	биоинформатики Инструмент
Лицензия	Программное обеспечение с открытым исходным кодом, сертифицированное OSI, по художественной лицензии.
Веб-сайт	ccb .джху .edu /программное обеспечение /мерцание /индекс .shtml

В биоинформатике прокариот GLIMMER (Gene Locator and Interpolated Markov ModelER) используется для поиска генов в ДНК . ^{[ 1 ]} «Он эффективен при поиске генов у бактерий , архей и вирусов , обычно обнаруживая 98-99% всех относительно длинных генов, кодирующих белок ». ^{[ 1 ]} GLIMMER была первой системой, использовавшей интерполированную марковскую модель. ^{[ 2 ]} для идентификации кодирующих регионов. Программное обеспечение GLIMMER имеет открытый исходный код и поддерживается Стивеном Зальцбергом , Артом Делчером и их коллегами из Центра вычислительной биологии. ^{[ 3 ]} в Университете Джонса Хопкинса . Оригинальные алгоритмы и программное обеспечение GLIMMER были разработаны Артом Делчером, Саймоном Касифом и Стивеном Зальцбергом и применены для аннотации бактериального генома в сотрудничестве с Оуэном Уайтом .

Версии

МЕРЦАНИЕ 1.0

Первая версия GLIMMER «т.е. GLIMMER 1.0» была выпущена в 1998 году и опубликована в статье « Идентификация генов микробов с использованием интерполированной модели Маркова ». ^{[ 1 ]} Марковские модели использовались для идентификации микробных генов в GLIMMER 1.0. GLIMMER учитывает локальные зависимости последовательности композиции, что делает GLIMMER более гибким и мощным по сравнению с марковской моделью фиксированного порядка .

было проведено сравнение интерполированной В статье « Идентификация генов микробов с использованием интерполированных моделей Маркова» модели Маркова, используемой GLIMMER, и модели Маркова пятого порядка . ^{[ 1 ]} «Алгоритм GLIMMER обнаружил 1680 генов из 1717 аннотированных генов у Haemophilus influenzae , тогда как модель Маркова пятого порядка обнаружила 1574 гена. GLIMMER обнаружил 209 дополнительных генов, которые не были включены в 1717 аннотированных генов, тогда как модель Маркова пятого порядка обнаружила 104 гена». ^{[ 1 ]}

МЕРЦАНИЕ 2.0

Вторая версия GLIMMER, то есть GLIMMER 2.0, была выпущена в 1999 году и опубликована в статье « Улучшенная идентификация микробов с помощью GLIMMER» . ^{[ 4 ]} Этот документ ^{[ 4 ]} обеспечивает значительные технические улучшения, такие как использование интерполированной контекстной модели вместо интерполированной модели Маркова и разрешение перекрывающихся генов, что повышает точность GLIMMER.

Вместо интерполированной модели Маркова используются интерполированные контекстные модели , что дает возможность выбора любой базы. В интерполированной марковской модели распределение вероятностей базы определяется на основе непосредственно предшествующих базисов. Если непосредственно предшествующее основание представляет собой трансляцию нерелевантной аминокислоты , интерполированная модель Маркова по-прежнему учитывает предыдущее основание для определения вероятности данного основания, тогда как модель интерполированного контекста, которая использовалась в GLIMMER 2.0, может игнорировать нерелевантные основания. Ложноположительные прогнозы были увеличены в GLIMMER 2.0, чтобы уменьшить количество ложноотрицательных прогнозов. Перекрывающиеся гены также решены в GLIMMER 2.0.

В статье « Улучшенная идентификация микроорганизмов с помощью GLIMMER» были проведены различные сравнения между GLIMMER 1.0 и GLIMMER 2.0. ^{[ 4 ]} который показывает улучшение в более поздней версии. «Чувствительность GLIMMER 1.0 колеблется от 98,4 до 99,7% со средним значением 99,1%, тогда как GLIMMER 2.0 имеет диапазон чувствительности от 98,6 до 99,8% со средним значением 99,3%. GLIMMER 2.0 очень эффективен при поиске генов высокой плотности. паразит Trypanosoma brucei , ответственный за африканскую сонную болезнь , идентифицирован GLIMMER 2.0" ^{[ 4 ]}

МЕРЦАНИЕ 3.0

Третья версия GLIMMER, «GLIMMER 3.0», была выпущена в 2007 году и опубликована в статье « Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer» . ^{[ 5 ]} В этой статье описывается несколько основных изменений, внесенных в систему GLIMMER, включая улучшенные методы идентификации кодирующих областей и стартового кодона . Оценка ORF в GLIMMER 3.0 выполняется в обратном порядке, т.е. начиная со стоп-кодона и возвращаясь к стартовому кодону. Обратное сканирование помогает более точно идентифицировать кодирующую часть гена, которая содержится в контекстном окне IMM. GLIMMER 3.0 также улучшает сгенерированные данные обучающего набора, сравнивая длинную ORF с универсальным распределением аминокислот в сильно различающихся бактериальных геномах. GLIMMER 3.0 имеет средний выход длинной ORF 57% для различных организмов, тогда как GLIMMER 2.0 имеет -Выход ORF 39%.» ^{[ 5 ]}

GLIMMER 3.0 снижает количество ложноположительных прогнозов, которые были увеличены в GLIMMER 2.0, чтобы уменьшить количество ложноотрицательных прогнозов. «GLIMMER 3.0 имеет точность предсказания стартового сайта 99,5% для совпадений 3 фута 5 футов, тогда как GLIMMER 2.0 имеет 99,1% для совпадений 3 фута 5 футов. GLIMMER 3.0 использует новый алгоритм для сканирования областей кодирования, новый модуль обнаружения стартового сайта. и архитектуру, которая объединяет все предсказания генов по всему геному». ^{[ 5 ]}

Минимальная длина описания

Теоретико-биологический фонд

Проект GLIMMER помог внедрить и популяризировать использование моделей переменной длины в вычислительной биологии и биоинформатике, которые впоследствии были применены к многочисленным проблемам, таким как классификация белков и другие. Моделирование переменной длины первоначально было предложено теоретиками информации, а затем изобретательно применено и популяризировано при сжатии данных (например, сжатие Зива-Лемпеля). Прогнозирование и сжатие тесно связаны с использованием принципов минимальной длины описания . Основная идея — создать словарь часто встречающихся слов (мотивов в биологических последовательностях). Интуиция подсказывает, что часто встречающиеся мотивы, вероятно, будут наиболее предсказуемыми и информативными. В GLIMMER интерполированная модель представляет собой смесь вероятностей этих относительно распространенных мотивов. Подобно развитию HMM в вычислительной биологии, на авторов GLIMMER концептуально повлияло предыдущее применение другого варианта интерполированных моделей Маркова для распознавания речи такими исследователями, как Фред Джелинек (IBM) и Эрик Ристад (Принстон). Алгоритм обучения в GLIMMER отличается от предыдущих подходов.

Доступ

GLIMMER можно загрузить с домашней страницы The Glimmer C++ (требуется компилятор ). Альтернативно, онлайн-версия размещена на сервере NCBI [1] .

Как это работает

GLIMMER в первую очередь ищет длинные ORFS . Открытая рамка считывания может перекрываться с любой другой открытой рамкой считывания, что будет разрешено с использованием метода, описанного в подразделе. Используя эти длинные ORFS и следуя определенному распределению аминокислот, GLIMMER генерирует данные обучающего набора .
Используя эти обучающие данные, GLIMMER обучает все шесть марковских моделей кодирующей ДНК от нулевого до восьмого порядка, а также обучает модель некодирующей ДНК.
GLIMMER пытается вычислить вероятности на основе данных. На основании количества наблюдений GLIMMER определяет, использовать ли модель Маркова фиксированного порядка или интерполированную модель Маркова.
1. Если количество наблюдений превышает 400, GLIMMER использует марковскую модель фиксированного порядка для получения вероятностей.
2. Если количество наблюдений меньше 400, GLIMMER использует интерполированную модель Маркова, которая кратко объясняется в следующем подразделе.
GLIMMER получает оценку для каждой длинной ORF, сгенерированной с использованием всех шести моделей кодирующей ДНК, а также с использованием модели некодирующей ДНК.
Если оценка, полученная на предыдущем шаге, превышает определенный порог, GLIMMER прогнозирует, что это ген.

Описанные выше шаги описывают базовую функциональность GLIMMER. В GLIMMER внесены различные улучшения, некоторые из них описаны в следующих подразделах.

Система ГЛИММЕР

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

вероятность для каждого основания, т. е. A,C,G,T для всех k-меров Вычисляется для 0 ≤ k ≤ 8. Затем для каждого k-мера GLIMMER вычисляет вес. Вероятность новой последовательности вычисляется следующим образом.

\operatorname {P(S|M)=\sum _{x=1}^{n}{IMM_{8}(S_{x})}}

где n — длина последовательности $S_{x}$ представляет собой олигомер в положении x. $IMM_{8}(S_{x})$ , $8^{th}$ марковской модели -порядка Оценка интерполированной вычисляется как

\operatorname {IMM_{k}(S_{x})=Y_{k}(S_{x-1})\cdot P_{k}(S_{x})+[1-{Y_{k}(S_{x-1})]\cdot IMM_{k-1}(S_{x})}}

"где $Y_{k}(S_{x-1})$ - вес k-мера в положении x-1 в последовательности S и $P_{k}(S_{x})$ — это оценка, полученная на основе обучающих данных вероятности того, что база находится в позиции x в $k^{th}$ -модель заказа». ^{[ 1 ]}

Вероятность основания $S_{x}$ учитывая i предыдущих базисов, вычисляется следующим образом.

\operatorname {P_{i}(S_{x})=P(s_{x}|S_{x,j})={\frac {f(S_{x,j})}{\sum _{b\in {[acgt]}}\operatorname {f(S_{x,i},b)} }}}

«Ценность $Y_{i}(S_{x})$ связанный с $P_{i}(S_{x})$ можно рассматривать как меру уверенности в точности этой величины как оценки истинной вероятности. GLIMMER использует два критерия для определения $Y_{i}(S_{x})$ . Первый из них — это простая частота появления, при которой количество вхождений контекстной строки $S_{x,i}$ в обучающих данных превышает определенное пороговое значение, то $Y_{i}(S_{x})$ установлено значение 1,0. Текущее значение порога по умолчанию — 400, что дает 95 % достоверности. Если выборочных вхождений контекстной строки недостаточно, build-imm использует дополнительные критерии для определения $Y$ ценить. Для данной контекстной строки $S_{x,i}$ длины i, build-imm сравните наблюдаемые частоты следующей базы $f(S_{x,i},a)$ , $f(S_{x,i},c)$ , $f(S_{x,i},g)$ , $f(S_{x,i},t)$ с ранее рассчитанными вероятностями интерполированной модели Маркова с использованием следующего более короткого контекста, $IMM_{i-1}(S_{x,{i-1}},a)$ , $IMM_{i-1}(S_{x,{i-1}},c)$ , $IMM_{i-1}(S_{x,{i-1}},g)$ , $IMM_{i-1}(S_{x,{i-1}},t)$ . Используя $X^{2}$ test, build-imm определяет, насколько вероятно, что четыре наблюдаемые частоты соответствуют значениям IMM из следующего более короткого контекста». ^{[ 1 ]}

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

Уравнения и пояснения к использованным выше терминам взяты из статьи «Идентификация генов микробов с использованием интерполированных моделей Маркова». ^{[ 1 ]}

Разрешение перекрывающихся генов

В GLIMMER 1.0, когда два гена A и B перекрываются, область перекрытия оценивается. Если A длиннее, чем B, и если A имеет более высокий балл в области перекрытия, и если перемещение стартового сайта B не устранит перекрытие, то B отклоняется.

GLIMMER 2.0 предоставил лучшее решение для устранения дублирования. В GLIMMER 2.0, когда два потенциальных гена A и B перекрываются, область перекрытия оценивается. Предположим, что балл гена А выше, рассматриваются четыре разные ориентации.

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

В приведенном выше случае перемещение B может устранить перекрытие, A и B можно назвать неперекрывающимися генами, но если B значительно короче, чем A, то B отвергается.

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

В приведенном выше случае можно перемещать как A, так и B. Сначала мы перемещаем начало B до тех пор, пока область перекрытия не получит более высокий балл для B. Затем мы перемещаем начало A, пока он не получит более высокий балл. Затем снова B и так далее, пока перекрытие не будет устранено или дальнейшие ходы станут невозможны.

Приведенный выше пример был взят из статьи «Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer». ^{[ 5 ]}

Сайты связывания рибосом

Сигнал сайта связывания рибосомы (RBS) можно использовать для определения истинного положения стартового сайта. Результаты GLIMMER передаются в качестве входных данных для программы RBSfinder для прогнозирования сайтов связывания рибосом. GLIMMER 3.0 интегрирует программу RBSfinder в саму функцию прогнозирования генов.

Программное обеспечение ELPH (которое в статье было признано высокоэффективным при идентификации RBS). ^{[ 5 ]}) используется для идентификации RBS и доступен на этом веб-сайте. Архивировано 27 ноября 2013 г. на Wayback Machine . Алгоритм выборки Гиббса используется для идентификации общего мотива в любом наборе последовательностей. Эти общие последовательности мотивов и их длина задаются в качестве входных данных для ELPH. Затем ELPH вычисляет матрицу весов позиций (PWM), которая будет использоваться GLIMMER 3 для оценки любого потенциального RBS, найденного RBSfinder. Вышеописанный процесс выполняется, когда у нас имеется значительное количество обучающих генов. Если обучающих генов недостаточно, GLIMMER 3 может загрузиться и сгенерировать набор прогнозов генов, которые можно использовать в качестве входных данных для ELPH. ELPH теперь вычисляет ШИМ, и эту ШИМ можно снова использовать на том же наборе генов, чтобы получить более точные результаты для стартовых участков. Этот процесс можно повторять для многих итераций, чтобы получить более последовательные результаты ШИМ и прогнозирования генов.

Производительность

Glimmer поддерживает усилия по аннотированию геномов широкого спектра бактерий, архей и вирусов. В ходе крупномасштабной повторной аннотации в Банке данных ДНК Японии (DDBJ, который является зеркальным отражением Genbank ). Косуге и др. (2006) ^{[ 6 ]} изучили методы поиска генов, использованные для 183 геномов. Они сообщили, что из этих проектов Glimmer был искателем генов в 49%, за ним следовал GeneMark с 12%, а другие алгоритмы использовались в 3% или меньше проектов. (Они также сообщили, что в 33% геномов использовались «другие» программы, а это во многих случаях означало, что они не могли идентифицировать метод. За исключением этих случаев, Glimmer использовался для 73% геномов, для которых методы можно было однозначно идентифицировать. ) Glimmer использовался DDBJ для повторной аннотации всех бактериальных геномов в Международной базе данных нуклеотидных последовательностей. ^{[ 7 ]} Эта группа также использует его для аннотирования вирусов. ^{[ 8 ]} Глиммер является частью конвейера бактериальных аннотаций в Национальном центре биотехнологической информации (NCBI). ^{[ 9 ]} которая также поддерживает веб-сервер для Glimmer, ^{[ 10 ]} как и сайты в Германии, ^{[ 11 ]} Канада. ^{[ 12 ]}

По данным Google Scholar, по состоянию на начало 2011 года оригинальная статья Glimmer (Salzberg et al., 1998) ^{[ 1 ]} цитировалось 581 раз, а статья Glimmer 2.0 (Delcher et al., 1999) ^{[ 4 ]} цитировалось 950 раз.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Зальцберг, СЛ; Делчер, Алабама; Касиф, С.; Уайт, О. (1998). «Идентификация микробных генов с использованием интерполированных марковских моделей» . Исследования нуклеиновых кислот . 26 (2): 544–548. дои : 10.1093/нар/26.2.544 . ПМК 147303 . ПМИД 9421513 .
^ Зальцберг, СЛ; Пертеа, М.; Делчер, Алабама; Гарднер, MJ; Теттелин, Х. (1999). «Интерполированные марковские модели для поиска генов эукариот». Геномика . 59 (1): 24–31. CiteSeerX 10.1.1.126.431 . дои : 10.1006/geno.1999.5854 . ПМИД 10395796 .
^ «Центр вычислительной биологии» . Университет Джонса Хопкинса . Проверено 23 марта 2013 г.
^ Перейти обратно: ^а ^б ^с ^д ^и Делчер, А.; Хармон, Д.; Касиф, С.; Уайт, О.; Зальцберг, С. (1999). «Улучшенная идентификация микробных генов с помощью GLIMMER» . Исследования нуклеиновых кислот . 27 (23): 4636–4641. дои : 10.1093/нар/27.23.4636 . ПМК 148753 . ПМИД 10556321 .
^ Перейти обратно: ^а ^б ^с ^д ^и Делчер, Алабама; Братке, К.А.; Пауэрс, ЕС; Зальцберг, СЛ (2007). «Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer» . Биоинформатика . 23 (6): 673–679. doi : 10.1093/биоинформатика/btm009 . ПМК 2387122 . ПМИД 17237039 .
^ Косуге, Т.; Абэ, Т.; Окидо, Т.; Танака, Н.; Хирахата, М.; Маруяма, Ю.; Машима, Дж.; Томики, А.; Курокава, М.; Химено, Р.; Фукучи, С.; Миядзаки, С.; Годобори, Т.; Татено, Ю.; Сугавара, Х. (2006). «Исследование и классификация возможных генов из 183 бактериальных штаммов с помощью общего протокола идентификации новых генов: путь генов в пространстве прокариот (GTPS)» . Исследования ДНК . 13 (6): 245–254. дои : 10.1093/dnares/dsl014 . PMID 17166861 .
^ Сугавара, Х.; Абэ, Т.; Годобори, Т.; Татено, Ю. (2007). «DDBJ работает над оценкой и классификацией бактериальных генов INSDC» . Исследования нуклеиновых кислот . 35 (Проблема с базой данных): D13–D15. дои : 10.1093/нар/gkl908 . ПМК 1669713 . ПМИД 17108353 .
^ Хирахата, М.; Абэ, Т.; Танака, Н.; Кувана, Ю.; Сигэмото, Ю.; Миядзаки, С.; Сузуки, Ю.; Сугавара, Х. (2007). «Брокер геномной информации для вирусов (GIB-V): база данных для сравнительного анализа геномов вирусов» . Исследования нуклеиновых кислот . 35 (Проблема с базой данных): D339–D342. дои : 10.1093/нар/gkl1004 . ПМЦ 1781101 . ПМИД 17158166 .
^ «Конвейер автоматического аннотирования геномов прокариот NCBI (PGAAP)» . Центр биоинформатики и вычислительной биологии . Проверено 23 марта 2012 г.
^ «Инструменты аннотации микробного генома» . Центр биоинформатики и вычислительной биологии . Проверено 23 марта 2012 г.
^ «ТиКо» . Институт микробиологии и генетики Геттингенского университета. 11 февраля 2005 г. Архивировано из оригинала 31 марта 2022 г. Проверено 23 марта 2012 г.
^ «Система бактериальных аннотаций BASys» . Архивировано из оригинала 24 июля 2012 года . Проверено 23 марта 2012 г.

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

Домашняя страница Glimmer в CCB, Университет Джонса Хопкинса , с которой можно загрузить программное обеспечение.

[Salzberg-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Зальцберг, СЛ; Делчер, Алабама; Касиф, С.; Уайт, О. (1998). «Идентификация микробных генов с использованием интерполированных марковских моделей» . Исследования нуклеиновых кислот . 26 (2): 544–548. дои : 10.1093/нар/26.2.544 . ПМК 147303 . ПМИД 9421513 .

[Pertea-2] Зальцберг, СЛ; Пертеа, М.; Делчер, Алабама; Гарднер, MJ; Теттелин, Х. (1999). «Интерполированные марковские модели для поиска генов эукариот». Геномика . 59 (1): 24–31. CiteSeerX 10.1.1.126.431 . дои : 10.1006/geno.1999.5854 . ПМИД 10395796 .

[3] «Центр вычислительной биологии» . Университет Джонса Хопкинса . Проверено 23 марта 2013 г.

[Delcher-4] Перейти обратно: ^а ^б ^с ^д ^и Делчер, А.; Хармон, Д.; Касиф, С.; Уайт, О.; Зальцберг, С. (1999). «Улучшенная идентификация микробных генов с помощью GLIMMER» . Исследования нуклеиновых кислот . 27 (23): 4636–4641. дои : 10.1093/нар/27.23.4636 . ПМК 148753 . ПМИД 10556321 .

[Bratke-5] Перейти обратно: ^а ^б ^с ^д ^и Делчер, Алабама; Братке, К.А.; Пауэрс, ЕС; Зальцберг, СЛ (2007). «Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer» . Биоинформатика . 23 (6): 673–679. doi : 10.1093/биоинформатика/btm009 . ПМК 2387122 . ПМИД 17237039 .

[Kosuge-6] Косуге, Т.; Абэ, Т.; Окидо, Т.; Танака, Н.; Хирахата, М.; Маруяма, Ю.; Машима, Дж.; Томики, А.; Курокава, М.; Химено, Р.; Фукучи, С.; Миядзаки, С.; Годобори, Т.; Татено, Ю.; Сугавара, Х. (2006). «Исследование и классификация возможных генов из 183 бактериальных штаммов с помощью общего протокола идентификации новых генов: путь генов в пространстве прокариот (GTPS)» . Исследования ДНК . 13 (6): 245–254. дои : 10.1093/dnares/dsl014 . PMID 17166861 .

[Sugawara-7] Сугавара, Х.; Абэ, Т.; Годобори, Т.; Татено, Ю. (2007). «DDBJ работает над оценкой и классификацией бактериальных генов INSDC» . Исследования нуклеиновых кислот . 35 (Проблема с базой данных): D13–D15. дои : 10.1093/нар/gkl908 . ПМК 1669713 . ПМИД 17108353 .

[Hirata-8] Хирахата, М.; Абэ, Т.; Танака, Н.; Кувана, Ю.; Сигэмото, Ю.; Миядзаки, С.; Сузуки, Ю.; Сугавара, Х. (2007). «Брокер геномной информации для вирусов (GIB-V): база данных для сравнительного анализа геномов вирусов» . Исследования нуклеиновых кислот . 35 (Проблема с базой данных): D339–D342. дои : 10.1093/нар/gkl1004 . ПМЦ 1781101 . ПМИД 17158166 .

[9] «Конвейер автоматического аннотирования геномов прокариот NCBI (PGAAP)» . Центр биоинформатики и вычислительной биологии . Проверено 23 марта 2012 г.

[10] «Инструменты аннотации микробного генома» . Центр биоинформатики и вычислительной биологии . Проверено 23 марта 2012 г.

[11] «ТиКо» . Институт микробиологии и генетики Геттингенского университета. 11 февраля 2005 г. Архивировано из оригинала 31 марта 2022 г. Проверено 23 марта 2012 г.

[12] «Система бактериальных аннотаций BASys» . Архивировано из оригинала 24 июля 2012 года . Проверено 23 марта 2012 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]