Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Оценка достоверности кластеров функционально-значимых фрагментов биологических последовательностей

Диссертация: Оценка достоверности кластеров функционально-значимых фрагментов биологических последовательностей
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Для решения задачи поиска локальных сходств, как правило, применяются фильтрационные методы. В частности, именно так работают программы для поиска локальных сходств, такие как BLAST, Owen, YASS. Эти методы основаны на предварительной фильтрации пространства поиска. Сначала находят короткие гомологичные фрагменты последовательностей (якоря или затравочные сходства). Затем якоря расширяют… Читать ещё >

Содержание

  • Глава 1. Обзор литературы
    • 1. 1. Мотивы биологических последовательностей и их вхождения
    • 1. 2. Вероятностные модели
    • 1. 3. Методы вычисления Р-значения кластера вхождений мотива
    • 1. 4. Сходства биологических последовательностей
    • 1. 5. Затравки
  • Глава 2. Теоретическая основа алгоритма SufPref
    • 2. 1. Постановка задачи
    • 2. 2. Перекрытия слов в мотиве. Граф перекрытий
    • 2. 3. Среднее число перекрытий
    • 2. 4. Текстовые множества
    • 2. 5. Вероятности текстовых множеств
  • Глава 3. Алгоритм SufPref для вычисления /^значения участка, содержащего кластер вхождений мотива
    • 3. 1. Алгоритм SufPref для моделей Бернулли
    • 3. 2. Алгоритм SufPref для СММ
    • 3. 3. Алгоритм SufPref для Марковских моделей
    • 3. 4. Предварительные построения
    • 3. 5. Анализ сложности алгоритма SufPref
  • Глава 4. Программная реализация алгоритма SufPref и ее апробация
    • 4. 1. Программная реализация алгоритма SufPref
    • 4. 2. Сравнение программы SufPref с программой AhoPro
    • 4. 3. Оценка статистической значимости шаблонов неупорядоченных участков в белках
  • Глава 5. Построение классификационных затравок для нахождения локальных сходств аминокислотных последовательностей
    • 5. 1. Классификационные затравки. Основные определения
    • 5. 2. Классификационные алфавиты
    • 5. 3. Классификационные затравки

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

Актуальность темы

исследования.

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

1) уметь оценивать достоверность (функциональную значимость) найденного кластера вхождений мотива и 2) определять характерную для мотива последовательность мономеров.

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

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

Проблема оценки достоверности предсказанных функционально-значимых вхождений мотива возникает в различных областях биоинформатики. Среди ученых, внесших значительный вклад в решение этой проблемы, О. Берг, Д. Гильберт, В. Ю. Макеев, A.A. Миронов, Г. Нюэль, М. Ренье, П. фон Хиппель и ряд других. Примером области, где необходима оценка достоверности кластеров сайтов, является идентификации потенциальных кластеров сайтов связывания белков — факторов регуляции транскрипции (ССФРТ), т. е. участков ДНК, которые взаимодействуют с факторами транскрипции. Здесь мотив — это набор допустимых сайтов связывания данного фактора транскрипции. Во многих существующих программах распознавания кластеров ССФРТ отбор значимых результатов производится на основе вычисленного Р-значения. Сказанное выше определяет актуальность выбранной темы.

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

Для решения задачи поиска локальных сходств, как правило, применяются фильтрационные методы. В частности, именно так работают программы для поиска локальных сходств, такие как BLAST [92], Owen [96], YASS [99]. Эти методы основаны на предварительной фильтрации пространства поиска. Сначала находят короткие гомологичные фрагменты последовательностей (якоря или затравочные сходства). Затем якоря расширяют до выравниваний более длинных фрагментов путем анализа окрестностей якорей. Образец для поиска затравочных сходств называется затравкой. Фильтрационные методы работают достаточно быстро, однако ценой за это может быть понижение чувствительности (доли найденных сходств). Поэтому встает вопрос о таком выборе затравки, чтобы алгоритм работал быстро и при этом имел достаточно высокую чувствительность. Для нуклеотидных последовательностей в этом направлении были получены хорошие результаты. Для аминокислотных последовательностей единственным удовлетворительным решением этой проблемы стало использование векторных затравок.

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

Цели и задачи исследования.

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

Исходя из поставленной цели, были сформулированы следующие задачи:

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

2. Разработать алгоритмы для нахождения точного Р-значения кластера из г вхождений мотива, расположенного на участке длины п, относительно трех видов вероятностных моделей: моделей Бернулли, Марковских моделей данного порядка и скрытых Марковских моделей (СММ).

3. Реализовать разработанные алгоритмы в виде компьютерных программ.

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

5. Применить разработанные программы для анализа реальных аминокислотных последовательностей.

Научная новизна и теоретическая ценность работы.

Теоретическая ценность работы состоит в исследовании комбинаторных объектов, связанных с наборами слов, — графов перекрытий слов, а также классификационных затравок. Получена оценка для среднего количества перекрытий слов, входящих в случайный мотив при равномерном распределении вероятностей мотивов. Доказано, что среднее количество перекрытий линейно зависит от размера мотива и не зависит от его длины. Для мотивов, имеющих неравномерное распределение Бернулли, линейная зависимость среднего количества перекрытий от размера мотива была показана с помощью компьютерных экспериментов.

Для вычисления Р-значений был разработан и алгоритм 8и№геГ в трех модификациях, соответствующих трем видам вероятностных моделей: моделям Бернулли, Марковским моделям произвольного порядка и скрытым Марковским моделям (СММ). В разработанном алгоритме впервые был использован граф перекрытий слов, что обеспечило его преимущество в быстродействии по сравнению с ранее разработанными алгоритмами. В отличие от большинства аналогичных алгоритмов, время работы 8и? РгеГ в среднем не зависит от длины мотива и размера алфавита.

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

Практическое значение работы.

Практическое значение работы состоит в программной реализации разработанных алгоритмов. В частности, алгоритм 8и1Рге1? реализован в виде кросс-платформенного программного комплекса. Программа и исходные коды доступны через интернет по адресу: http://server2.lpm.org.ru/bio/online/sf. Реализация предложенного метода используется при создании опытного образца программного комплекса «СИМВОЛ», разрабатываемого в рамках государственного контракта № 07.514.11.4004. Результаты исследования использовались при выполнении работ по темам «Сравнительный анализ структур белков и нуклеиновых кислот» (номер государственной регистрации 01.2.409 635), «Математические методы анализа белков и нуклеиновых кислот: связь между последовательностями, структурой и функцией» (номер государственной регистрации 01.2.952 309), а также при выполнении проекта РФФИ 09−04−1 053-а «Достоверность и полнота результатов при компьютерном анализе последовательностей биополимеров».

Построенные классификационные алфавиты были использованы Л. Ноэ в программе УАБЗ (ЬЦр^ютГо.НА.йУуазз/). Эта программа успешно применяется для выравнивания аминокислотных последовательностей.

Основные положения, выносимые на защиту.

1. Разработанный алгоритм 8и? РгеГ корректно вычисляет вероятность (Р-значение) появления не менее г вхождений мотива Н, слова в котором имеют одинаковую длину т, в случайной последовательности длины праспределение вероятностей на множестве случайных последовательностей может задаваться с помощью моделей Бернулли, Марковских моделей произвольного порядка и скрытых Марковских моделей.

2. Размер используемой памяти и время работы алгоритма 8и1РгеГ описываются следующими формулами (ниже, А — используемый алфавит, 0¥-(Н) -множество перекрытий слов в мотиве Н):

— для моделей Бернулли: память: 0(гхтхУ (Н)+тхН) — время: 0{пуг*(У (Н)+Н)).

— для Марковских моделей порядка К: память: 0(г*КхАк+1+гхтхОУ (Н)+тх|Я|) — время: 0(пхгх (КхАк+1+Г (Щ+Н));

— для СММ: память: 0(|?|2 *(|0К (Я)|+|Я|)+|?| *г хт хОГ (Н)+т х|Я]) — время: 0(д2хпхгх (ОУ (Н)+Н])). Полученные оценки показали, что SufPref превосходит по характеристикам большинство существующих алгоритмов.

3. Среднее количество перекрытий слов в мотивах данного размера и данной длины при равномерном распределении вероятностей на множестве мотивов линейно зависит от размера мотивов и не зависит от их длины.

4. Разработанная методика построения классификационных алфавитов позволяет получать классификационные затравки, которые не уступают лучшим из ранее известных видов затравок по чувствительности и избирательности.

Структура и объем диссертации

.

Диссертация состоит из введения, пяти глав, заключения и списка литературы (130 наименований). Полный объем диссертации составляет 128 страниц, количество рисунков — 20, количество таблиц — 20.

ЗАКЛЮЧЕНИЕ

.

В диссертации представлены следующие основные результаты.

1. Разработан алгоритм SufPref для вычисления вероятности (Р-значения) появления не менее г вхождений заданного мотива в случайной последовательности длины п. Распределение вероятностей на множестве случайных последовательностей может задаваться с помощью моделей Бернулли, Марковских моделей порядка К, где К<�т, и скрытых Марковских моделей.

2. Получены оценки сложности работы алгоритма для указанных видов вероятностных моделей.

3. С помощью компьютерных экспериментов было показано, что среднее число перекрытий overlapavg (s, т) в случайных мотивах, слова в которых порождены в рамках моделей Бернулли, пропорционально количеству слов s в мотивах и не зависит от длины т этих слов. Для мотивов, слова в которых имеют равномерное распределение, была доказана теорема о том, что overlapavg (s, т) < c-s, где с — константа, зависящая от размера алфавитас < 4. Из этого следует, что скорость работы алгоритма в среднем не зависит от длины слов в мотиве.

4. Алгоритм SufPref реализован в виде кросс-платформенного программного комплекса.

5. Проведено сравнение реализации алгоритма SufPref с реализацией алгоритма AhoPro для модели Бернулли и Марковской модели первого порядка. Для модели Бернулли SufPref работает в 4 — 20 раз быстрее AhoPro и использует в среднем в полтора раза меньше памяти. Для Марковской модели SufPref работает в 2 — 5 раз быстрее AhoPro, но проигрывает по размеру используемой памяти не более чем на 20%.

6. Вычислены Р-значения и статистические значимости вхождений мотивов неупорядоченных участков в белках.

7. Построены классификационные алфавиты для анализа аминокислотных последовательностей: (1) пороговый алфавит, (2) иерархический транзитивный алфавит- (3) неиерархический транзитивный алфавит. Затравки над этими алфавитами не уступают по чувствительности и избирательности лучшим из ранее известных видов затравок.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Roytberg M.A., GambinA., Noe L., Lasota S., Furletova E.I., SzczurekE., Kucherov G. On subset seeds for protein alignment. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2009. V. 6, N. 3. P. 483194.

2. Lobanov M.Y., Furletova E.I., BogatyrevaN.C., Roytberg M.A., Galzitskaya O.V. Library of disordered patterns in 3D protein structures. // PLoS Computational Biology. 2010. V. 6, N. 10. P. 1−10.

3.RegnierM., Kirakosian Z., Furletova E.I., Roytberg M.A. A word counting gpaph. // London algorithmics 2008: theory and practice. 2009. P. 10-^3.

4. Furletova E.I., Kucherov G., Noe L., Roytberg M.A., Tsitovich I.I. Statistical approach to the design of subset seeds for protein alignment. // Proceedings of the International Moscow Conference on computational molecular biology. July 2007. P. 94.

5. Furletova E.I., Kucherov G., NoeL., Roytberg M.A., Tsitovich I.I. Transitive subset seeds for protein alignment. // Proceedings of the 6th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS). July 2008, Novosibirsk (Russia). P. 77.

6. Roytberg M.A., Gambin A., Noe L., Lasota S., Furletova E.I., Szczurek E., Kucherov G. Efficient seeding techniques for protein similarity search. // Proceedings of the 2nd International Conference BIRD-ALBIO. 2008. P. 466 478.

7. Regnier M., Furletova E.I., Roytberg M.A. An average number of suffix-prefixes. // Proceedings of the International Moscow Conference on computational molecular biology. 2009. P. 313−314.

8. Regnier M., Furletova E.I., Roytberg M.A., Yakovlev V.V. An algorithm for exact probability of pattern occurrences calculation. // Proceedings of the International Moscow Conference on computational molecular biology. 2011. P. 320.

Показать весь текст

Список литературы

  1. Zhang J., Jiang B., LiM., Tromp J., Zhang X., Zhang M. Computing exact p-values for DNA motifs. // Bioinformatics. 2006. Vol.23. P. 531−537. doi: 10.1093/bioinformatics/btl662.
  2. Leung M.Y., Marsh G.M., Speed T.P. Over and underrepresentation of short
  3. DNA words in Herpesvirus genomes. // Journal of Computational Biology. 1996. V 3. P. 345−360.
  4. RochaE., ViariA., DanchinA. Oligonucleotide bias in Bacillus subtilis: general trends and taxonomic comparisons. // Nucleic Acids Research. 1998. V. 26. P.2971−2980.
  5. Karlin S., Burge C., Campbell A. Statistical analyses of counts and distributionsof restriction sites in DNA sequences. // Nucleic Acids Research. 1992. V. 20. N. 6. P. 1363−1370.
  6. Sourice S., Biaudet V., Karoui M., Ehrlich S., Gruss A. Identification of the Chisite of Haemophilus influenzae as several sequences related to Escherichia coli Chi site. // Molecular Microbiology. 1998. V. 27. P. 1021−1029.
  7. Stormo G.D. DNA binding sites: representation and discovery // Bioinformatics. 2000. V. 16, N. 1. P. 16−23.
  8. Lawrence, C.E., et al. Detecting subtle sequence signals: a Gibbs samplingstrategy for multiple alignment. // Science. 1993. V. 262, N. 5131. P. 208−214.
  9. Bailey T.L. and Elkan C. The value of prior knowledge in discovering motifswith MEME. // Proceedings of International Conference on Intelligent Systems for Molecular Biology. 1995. V. 3. P. 21−29.
  10. Hertz G.Z. and Stormo G.D. Identifying DNA and protein patterns withstatistically significant alignments of multiple sequences. // Bioinformatics. 1999. V. 15, N. 7. P. 563−577.
  11. Hertz G.Z., Hartzell G.W. and Stormo G.D. Identification of consensus patterns in unaligned DNA sequences known to be functionally related. // Computer Applications in the Biosciences. 1990. V. 6, N. 2. P. 81−92.
  12. Pevzner P.A. and Sze S.H. Combinatorial approaches to finding subtle signals in DNA sequences // Proceedings of International Conference on Intelligent Systems for Molecular Biology. 2000. V. 8. P. 269−278.
  13. Sze S.H., Gelfand M.S. and Pevzner P.A. Finding weak motifs in DNA sequences. // Pacific Symposium on Biocomputing. 2002. P. 235−246.
  14. Buhler J. and Tompa M. Finding motifs using random projections. // Journal of Computational Biology. 2002. V. 9, N. 2. P. 225−242.
  15. Rouchka E.C. A Brief Overview of Gibbs Sampling. 1997.
  16. EskinE. and PevznerP.A. Finding composite regulatory patterns in DNA sequences. // Bioinformatics. 2002. V. 18, Suppl. 1. P. S354-S363.
  17. Gribskov M., Devereux J. Sequence Analysis Primer. // New York: Stockton Press. 1991.
  18. Gribskov M, LuthyR., Eisenberg D. Profile analysis II Methods in Enzymology.
  19. Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. 1990. V. 183. P. 146−159.
  20. Gribskov M., McLachlan A., Eisenberg D. Profile analysis detection of distantly related proteins. // Proceedings of the National Academy of Science. USA, 1987. V. 88. P. 4355^1358.
  21. А.А. и ГельфандМ.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Участки связывания PurR. // Молекулярная биология. 1999. Т. 33, № 1. С. 127−132.
  22. Favorov A.V., et al. A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length. // Bioinformatics. 2005. V. 21, N. 10. P. 2240−2245.
  23. Bailey T.L. and ElkanC.P. Unsupervised learning of multiple motifs in biopolymersusing expectation maximization. // Machine Learning J. 1995. V. 21. P. 51−83.
  24. Nomenclature for Incompletely Specified Bases in Nucleic Acid Sequences. 1984.
  25. Leung M.Y., Marsh G.M., Speed T.P. Over and underrepresentation of short DNA words in Herpesvirus genomes. Journal of Computational Biology. 1996. V. 3. P. 345−360.
  26. Kucherov G., Noe L., Roytberg M.A. A unifying framework for seed sensitivity and its application to subset seeds. // Journal of Bioinformatics and Computational Biology. 2006. V. 4, N. 2. P. 553−570.
  27. Durbin R., Eddy D., Krogh A., Mitchison G. Markov chains and hidden Markov models. Biological sequence analyses. // CambridgeUniversity Press. 1998. P. 46−79.
  28. Nicolas P., Bize L., Muri F., Hoebeke M., Rodolphe F., Ehrlich S., Prum В., Bessieres P. Mining Bacillus subtilis chromosome heterogeneities using hidden Markov models. // Nucleic Acids Research. 2002. V. 30. P. 1418−1426.
  29. Martin J., Gibrat J., Rodolphe F. Analysis of an optimal hidden Markov model for secondary structure prediction. // BMC Structural Biology. 2006. V6. P. 25.
  30. Aston J.A.D., Martin D.E.K. Distributions associated with general runs and patterns in hidden Markov models. // Annals Applied Statistics. 2007. V. 1, N. 2. P. 585−611.
  31. Wagner R.A., Fischer M.J. The String-to-String Correction Problem. // Journal of ACM. 1974. V. 21, N. 1. P. 168−173.
  32. Cowan R. Expected frequencies of DNA patterns using Whittle’s formula. // Journal of Applied Probability. 1991. V. 28. P. 886−892.
  33. Kleffe J., Borodovski M. First and second moment of counts of words in random texts generated by Markov chains. // Bioinformatics. 1997. V. 8, N. 5. P. 433−441.
  34. Prum B., Rodolphe F., de Turckheim E. Finding words with unexpected frequencies in DNA sequences. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 1995. V. 11. P. 190−192.
  35. NuelG. S-SPatt: simple statistics for patterns on Markov chains. // Bioinformatics. 2005. V. 21, N. 13. P. 3051−3052.
  36. Godbole A.P. Poissons approximations for runs and patterns of rare events. // Advances in Applied Probability. 1991. V. 23. P. 851−865.
  37. Geske M.X., Godbole A.P., Schaffner A.A., Skrolnick A.M., Wallstrom G.L. Compound Poisson approximations for word patterns under Markovian hypotheses. // Journal of Applied Probability. 1995. V. 32. P. 877−892.
  38. Reinert G., Schbath S. Compound Poisson and Poisson process approximations for occurrences of multiple words in Markov chains. // Journal of Computational Biology. 1999. V. 5. P. 223−254.
  39. Erhardsson T. Compound Poisson approximation for counts of rare patterns in Markov chains and extreme sojourns in birth-death chains. // Annals of Applied Probability. 2000. V. 10, N. 2. P. 573−591.
  40. Nuelg G. Cumulative distribution function of a geometric Poisson distribution. Journal of Statistical Computation and Simulation. 2008. V. 78. N. 3. P. 211— 220.
  41. DeniseA., RegnierM., Vandenbogaert M. Assessing the Statistical Significance of Overrepresented Oligonucleotides. // Lecture Notes in Computer Science. 2001. V. 2149. P. 85−97.
  42. Nuel G. LD-SPatt: Large Deviations Statistics for Patterns on Markov Chains. // Journal of Computational Biology. 2004. V. 11, N. 6. P. 1023−1033.
  43. Fu J., Johnson B. Approximate Probabilities for Runs and Patterns in i.i.d. and Markov Dependent Multi-state Trials. // Advances in Applied Probability 2009. V.41.P. 292−308.
  44. Regnier M. and Szpankowski W. On Pattern Frequency Occurrences in a Markovian Sequence. //Algorithmica. 1997. V. 22, N. 4. P. 631−649.
  45. Lothaire. M. Statistics on Words with Applications to Biological Sequences. Applied combinatorics on words. // Encyclopedia of Mathematics and its Applications. Cambridge University Press. 2004. V. 105.
  46. Reinert G, Schbath S, Waterman MS Probabilistic and statistical properties of words: an overview. // Journal of Computational Biology. 2000. V. 7, N. 1−2. P. 1−46.
  47. Nuel G. Numerical solutions for Patterns Statistics on Markov chains. // Statistical Applications in Genetics and Molecular Biology. 2006. V. 5, N. 1. P. 26.
  48. Nuel G. On the first k moments of the random count of a pattern in a multi-states sequence generated by a Markov source. 2010. // Journal of Applied Probability. V. 47. P. 1−19.
  49. Blinnikov S. and Moessner R. Expansions for nearly Gaussian distributions. // Astronomy and Astrophysics Supplement Series. 1998. V. 130. P. 193−205.
  50. Regnier M., Vandenbogaert M. Statistical Significance Criteria revisited. // Journal of Bioinformatics and Computational Biology. 2005. V. 4, N. 2. P. 537−551.
  51. Hertzberg L., ZukO., GetzG., DomanyE. Finding Motifs in Promoter Regions. // Journal of Computational Biology. 2005. V. 12, N. 3. P. 314−330.
  52. Robin S., Daudin J.-J. Exact distribution of word occurrences in a random sequence of letters. // Journal of Applied Probability. 1999. V. 36. P. 179−193.
  53. Chrysaphinou C., Papastavridis S. The Occurrence of Sequence of Patterns in Repeated Dependent Experiments. Theory of Probability and Applications. 1990. V. 79. P. 167−173.
  54. Nuel G. Effective /"-value computations using Finite Markov Chain Imbedding (FMCI): application to local score and to pattern statistics. // Algorithms for Molecular Biology. 2006. V. 1, N. 1. P. 5.
  55. Nuel G. Exact distribution of a pattern in a set of random sequences generated by a Markov source: applications to biological data. // Algorithms for Molecular Biology. 2010. V. 5. P. 15.
  56. М.А. Вычисление вероятностей семейств биологических последовательностей. // Биофизика. 2009. Т. 54. № 5. С. 718−724.
  57. Regnier M. A Unified Approach to Word Occurrences Probabilities. // Discrete Applied Mathematics. 2000. V. 104. N. 1. P. 259−280.
  58. Boeva V., Clement J., Regnier M., Vandenbogaert M. Assessing the Significance of Sets of Words. // Combinatorial Pattern Matching 05, Lecture Notes in Computer Science. 2005. V. 3537. P. 358−370.
  59. Nicodeme P. Regexpcount, a symbolic package for counting problems on regular expressions and words. // Fundamenta Informatica. 2003. V. 56, N. 12. P. 71−88.
  60. Regnier M. and Denise A. Rare events and conditional events on random strings. // Journal of Discrete Mathematics and Theoretical Computer Science. 2004. V. 6, № 2. P. 191−214.
  61. Regnier M. Mathematical tools for regulatory signals extraction. // Proceedings of Bioinformatics of Genome Regulation and Structure. 2002. V. l.P. 17−19.
  62. AhoA.V., CorasickM.J. Efficient string matching: An aid to bibliographic search. // Communications of the ACM. 1975. V. 18. P. 6.
  63. Tompa P. Intrinsically unstructured proteins. // Trends in Biochemical Sciences. 2002. V. 27, P. 527−533.
  64. Wright P.E., Dyson H.J. Intrinsically unstructured proteins: re-assessing the protein structure-function paradigm. // Journal of Molecular Biology. 1999. V. 293. P. 321−331.
  65. Dyson H.J., Wright P.E. Intrinsically unstructured proteins and their functions. //Nature Reviews Molecular Cell Biology. 2005. V. 6. 197−208.
  66. Galea C.A., Wang Y., Sivakolundu S.G., Kriwacki R.W. Regulation of cell division by intrinsically unstructured proteins: intrinsic flexibility, modularity, and signaling conduits. // Biochemistry. 2008. V. 47. P. 7598−7609.
  67. Fuxreiter M., Tompa P., Simon I., Uversky V.N., Hansen J.C., et al. Malleable machines take shape in eukaryotic transcriptional regulation. // Nature Chemical Biology. 2008. V. 4. P. 728−737.
  68. Sickmeier M., Hamilton J.A., LeGallT., VacicV., CorteseM.S., et al. DisProt: the Database of Disordered Proteins. // Nucleic Acids Research. 2007. V. 35. P. D786−793.
  69. Peterlongo P, Noe. L., LavenierD., Georges G., Jacques J., Kucherov G. Protein Similarity Search with Subset Seeds on a Dedicated Reconfigurable Hardware. // PPAM. 2007. P. 1240−1248
  70. Stebbings A., Mizuguchi K. HOMSTRAD: Recent developments of the homologous protein structure alignment database. // Nucleic Acids Research. 2004. V. 32. P. D203-D207.
  71. Subramanian A.R., Weyer-Menkho J., Kaufmann M., Morgenstern B. DIALIGN-T: an improved algorithm for segment-based multiple sequence alignment. // BMC Bioinformatics. 2005. V. 6, N. 66.
  72. Raghava G., Searle S., Audley P., Barber J., Barton G. OXBench: a benchmark for evaluation of protein multiple sequence alignment accuracy. // BMC Bioinformatics. 2003. V. 4, N. 47.
  73. Edgar R.C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. //Nucleic Acids Research. 2004. V. 32, N. 5. P. 1792−1797.
  74. Van Walle I., Lasters I., Wyns L. SABmark a benchmark for sequence alignment that covers the entire known fold space. // Bioinformatics. 2005. V. 21, N. 7. P. 1267−1268.
  75. Letunic I., Copley R, PilsB., Pinkert S., SchultzJ., BorkP. SMART5: domains in the context of genomes and networks. // Nucleic Acids Research. 2006. V. 34, N. 1. P. D257-D260.
  76. M.C. Геномы и эволюция. // Вестник РАН. 2009. Т. 79. С. 411 418
  77. Pearson W.R. Comparison of methods for searching protein sequence databases. // Protein Science. 1995. V. 4, N. 6. P. 1145−60.
  78. DayhoffM.O., Schwartz R. and Orcutt B.C. A model of Evolutionary Change in Proteins. // Atlas of protein sequence and structure. 1978. V. 5, N. 3. P. 345 358.
  79. Henikoff S.- Henikoff, J.G. Amino Acid Substitution Matrices from Protein Blocks. // Proceedings of the National Academy of Sciences of the United States of America. 1992. V. 89, N. 22, P. 10 915−10 919.
  80. Brenner S.A., Cohen M.A., GonnetG.H. Amino acid substitution during functionally constrained divergent evolution of protein sequences. // Protein Engineering, Design and Selection. 1994. P. 1323−1332.
  81. Waterman M.S. Sequence Alignments. // Mathematical Methods for DNA Sequences. 1989. P. 53−92.
  82. Gotoh O. An improved algorithm for matching biological sequences. // Journal of Bioinformatics and Computational Biology. 1982. V. 162, P. 705−708.
  83. Waterman M.S. Efficient sequence alignment algorithm. // Journal of Theoretical Biology. 1984. V. 108. P. 333−337.
  84. Waterman MS. Introduction to Computational Biology. 1985.
  85. Needlman S., Wunsch C. A general method applicable to the search for similarities in the amino acid sequence of two proteins. // Journal of Molecular Biology. 1970. V. 48. P. 443153.
  86. Smith T.F., Waterman M.S. Identification of common molecular sub sequences.//Journal of Molecular Biology. 1981. V. 147. P. 195−197.
  87. Lipman D.J., Pearson W.R. Rapid and sensitive protein similarity searches. // Science. 1985. V. 227. P. 1435−1441.
  88. Pearson W.R., Lipman D.J. Improved Tools for Biological Sequence Analysis. // Proceedings of the National Academy of Science. USA, 1988. V. 85, P. 2444−2448.
  89. Altschul S., GishW., Miller W., Myers E., Lipman D.J. Basic Local Alignment Search Tool. // Journal of Molecular Biology. 1990. V. 215. P. 403 410.
  90. Altschul S.F., BoguskiM.S., GishW., Wootton J.C. Issues in searching molecular sequence database. // Nature Genetics. 1994. V. 6. P. 119−129.
  91. Ma B., Tromp J., and Li M. PatternHunter: Faster and more sensitive homology search. //Bioinformatics. 2002. V. 18, N. 3. P. 440−445.
  92. Li M., Ma B., Kisman D., and Tromp J. PatternHunter II: Highly sensitive and fast homology search. Journal of Bioinformatics and Computational Biology. 2004. V. 2, N. 3. P. 417−439.
  93. Ogurtsov A.Y., Roytberg M.A., Shabalina S.A., Kondrashov A.S. OWEN: aligning long collinear regions of genomes. // Bioinformatics. 2002. V. 18. P.1703−1704.
  94. Roytberg M.A., Ogurtsov A.Y., Shabalina S.A., Kondrashov A.S. A hierarchical approach to aligning collinear regions of genomes. // Bioinformatics. 2002. V. 18. P. 1673−1680.
  95. NoeL. and KucherovG. YASS: enhancing the sensitivity of DNA similarity search. //Nucleic Acids Research. 2005. V. 33. P. W540-W543.
  96. Brejova B., Brown D., Vinar T. Optimal spaced seeds for homologous coding regions. // Journal of Bioinformatics and Computational Biology. 2004. V. 1. P. 595−610.
  97. Buhler J., KeichU., SunY. Designing Seeds for Similarity Search in Genomic DNA. // Preceedings of the 7th Annual International Conference on Research in Computational. 2003. P. 67−75.
  98. Choi K.P., ZengF., Zhang L. Good Spaced Seeds For Homology Search. //Bioinformatics. 2004. V. 20, P. 1053−1059.
  99. Choi K., Zhang L. Sensitivity analysis and efficient method for identifying optimal spaced seeds. // Journal of computer and System Sciences. 2004. V. 68, P. 220.
  100. NoeL., KucherovG. Improved Hit Criteria for DNA Local Alignment. // BMC Bioinformatics. 2004. V. 5, N. 149.
  101. Keich U., Li M., Ma В., Tromp J. On spaced seeds for similarity search. // Discrete Applied Mathematics. 2004. V. 138, N. 3. P. 253−263.
  102. BrejovaB., Brown D.G., and Vinar T. Vector seeds: An extension to spaced seeds. // Journal of Computer and System Sciences. 2005. V. 70, N. 3. P. 364 380.
  103. Fontaine M., Burkhardt S., and Karkkainen J. BDD-based analysis of gapped q-gram filters. // Proceedings of the 9th Prague Stringology Conference (PSC). 2004. P. 56−68.
  104. Xu J., Brown D.J., Li M., and Ma B. Optimizing multiple spaced seeds for homology search. // Journal of Computational Biology. 2006. V. 13, N. 7. P. 1355−1368.
  105. Kucherov G., NoeL., RoytbergM.A. Multiseed lossless filtration. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2005. V. 2. P. 51−61.
  106. Gao X., Li S.C., Lu Y. New algorithms for the spaced seeds. // In Frontiers of Algorithmic Workshop. 2007. V. 4613 of Lecture Notes in Computer Science. P. 51−61.
  107. Nicolas F. and Rivals E. Hardness of optimal spaced seed design. // Journal of Computer and System Sciences. 2008. V. 74, P. 831−849.
  108. NoeL., GirdeaM., and KucherovG. Designing efficient spaced seeds for SOLiD read mapping. // Advances in Bioinformatics. 2010. V. 2010. P. ID 708 501.
  109. В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. //Доклады Академий Наук СССР. 1965. Т. 163, № 4. С. 845−848.
  110. Brown D.J. Multiple vector seeds for protein alignment. // Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI). Bergen (Norway) 2004. V. 3240 of Lecture Notes in Bioinformatics. P. 170−181.
  111. Sun Y., Buhler J. Designing multiple simultaneous seeds for DNA similarity search. // Proceedings of the 8th Annual International Conference on Computational Molecular Biology. 2004.
  112. Brown D. Optimizing multiple seed for protein homology search. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2004. V. 2, N. l.P. 29−38.
  113. Nguyen V.H. and LavenierD. Speeding up subset seed algorithm for intensive protein sequence comparison. // Proceedings of the 6th IEEE International Conference on research. 2008. P. 57−63.
  114. Kent W.J., ZahlerA.M. Conservation, regulation, synteny and introns in a large-scale C. briggsae-C, elegans genomic alignment. // Genome Research. 2000. V. 10, N. 8. P. 1115−1125.
  115. Kent W.J. BLAT- the BLAST-like alignment tool. // Genome Research. 2002. V. 12, N. 4. P. 656−664.
  116. Roytberg M.A., GambinA., NoeL., Lasota S., Furletova E.I., SzczurekE., Kucherov G. On subset seeds for protein alignment. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2009. V. 6, N. 3. P. 483−494.
  117. Lobanov M.Y., Furletova E.I., Bogatyreva N.C., Roytberg M.A., Galzitskaya O.V. Library of disordered patterns in 3D protein structures. PLoS Computational Biology. 2010. V. 6, N. 10. P. 1−10.
  118. Regnier M., Kirakosian Z., Furletova E.I., Roytberg M.A. A word counting gpaph. // London algorithmics 2008: theory and practice. 2009. P. 10−43.
  119. Furletova E.I., Kucherov G., Noe L., Roytberg M.A., Tsitovich I.I. Statistical approach to the design of subset seeds for protein alignment. // Proceedings of the International Moscow Conference on computational molecular biology. July 2007. P. 94.
  120. Roytberg M. A., GambinA., NoeL., Lasota S., Furletova E.I., SzczurekE., Kucherov G. Efficient seeding techniques for protein similarity search. // Proceedings of the 2nd International Conference BIRD-ALBIO. 2008. P. 466 478.
  121. Regnier M., Furletova E.I., Roytberg M.A. An average number of suffix-prefixes. // Proceedings of the International Moscow Conference on computational molecular biology. 2009. P. 313−314.
  122. Regnier M., Furletova E.I., Roytberg M.A., Yakovlev V.V. An algorithm for exact probability of pattern occurrences calculation. // Proceedings of the International Moscow Conference on computational molecular biology. 2011. P. 320.
  123. Pollard D.A., Moses A.M., Iyer V.N., et al. Detecting the limits of regulatory element conservation and divergence estimation using pairwise and multiple alignments. // BMC Bioinformatics. 2006. V. 7. P. 376
  124. Dumas J.P., Ninio J. Efficient algorithms for folding and comparing nucleic acid sequences // Nucleic Acids Research. 1982. V. 10. P. 197 206.
  125. Korn L.J., Queen C.L., Wegman M.N. Computer analysis of nucleic acid regulatory sequences. // Proceedings of the National Academy of Science, USA, 1977. V. 74, N. 10. P. 4401−4405.
Заполнить форму текущей работой

На отлично!