Конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова

Россия, Новосибирск, Академгородок, 8 - 11 октября 2001 года,
(номер государственной регистрации 0320300063)

Тезисы докладов

Информационная биология

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

Евдокимов А.А., Левин А.А.

Институт математики им. С.Л.Соболева СО РАН (Новосибирск)

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

К таким структурам относятся, в частности, графы перекрытия слов, введенные де Брёйном в 1946 году [1]. Каждой символьной последовательности сопоставляется путь в таком графе, а заметаемые путем структуры (подграфы графов де Брёйна размерностей n=1,2,3, . . . ) содержат информацию как о локальном строении последовательности, так и о её свойствах "в целом", являясь удобным инструментом исследования различных задач о символных последовательностях [2].

Реализованная программа VIZ предназначена для визуализации символьных последовательностей на графах де Брёйна. Она написана на языке JAVA и работает на любой ЭВМ с виртуальной машиной JAVA. Последовательность структурных "портретов" анализируемых последовательностей выводится на экран, позволяя наблюдать динамику изменения свойств последовательностей. Программа позволяет проводить эксперименты с различными последовательностями:

  • математическими, определяемыми конструктивными процедурами порождения раличной степени сложности;
  • генетическими последовательностями ДНК с различными структурными и функциональными свойствами.

    Предусмотрены варьирование способа представления структурных портретов на экране и изменение параметров процесса, которые можно производить непосредственно в ходе наблюдения:

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

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

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

    Работа выполнена при поддержке программы "Интеграция"(АО - 110), гранта РФФИ 99-01-00531 и интеграционного проекта СО РАН N65.

      Литература:

    1. de Bruijn N.G. A combinatorial problem. Proc. Kon. Ned. Akad. v. Wet., 49 N7,1946, pp.758-764.(перевод см. Кибернетический сборник, новая серия, вып.6 М., Мир, 1969, С.33-40.)
    2. Евдокимов А.А. Полные множества слов и их числовые характеристики // Методы дискретного анализа в исследовании экстремальных структур: Сб. науч.тр. Новосибирск: Институт математики СО АН СССР, 1983, вып.39, С.7-19.
    3. Lothaire M. Combinatorics on words. Encyclopedia of mathematics and its applications. Addison - Wesley Publ. Company, 1983.

    Примечание. Тезисы докладов публикуются в авторской редакции

    Ваши комментарии
    		[SBRAS]
    [Головная страница]
    [Конференции]
    [СО РАН]

    © 2001, Сибирское отделение Российской академии наук, Новосибирск
    © 2001, Объединенный институт информатики СО РАН, Новосибирск
    © 2001, Институт вычислительных технологий СО РАН, Новосибирск
    © 2001, Институт систем информатики СО РАН, Новосибирск
    © 2001, Институт математики СО РАН, Новосибирск
    © 2001, Институт цитологии и генетики СО РАН, Новосибирск
    © 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
    © 2001, Новосибирский государственный университет
    Дата последней модификации 06-Jul-2012 (11:45:21)