Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kodomo.cmm.msu.ru/FBB/year_02/science_1/themes_2004f/Nikolaev.doc Дата изменения: Thu Dec 16 22:01:37 2004 Дата индексирования: Sat Dec 22 07:28:24 2007 Кодировка: koi8-r

Тема: Улучшение AliBee - Алгоритма Множественного Выравнивания.

Кураторы: А.М.Леонтович, В.К.Николаев, отдел математических методов в
биологии.
aml@genebee.msu.su, 932-88-25, комната 234, Лабораторный корпус "А"

Предлагаемая тема предполагает умение или, по крайней мере, желание
научиться программировать. Помощь и консультации по программированию
гарантируются.

Алгоритм построения множественного выравнивания последовательностей
является одним из центральных биоинформационных инструментов.
Один из таких алгоритмов (AliBee) разработан в GeneBee группе
(http://www.genebee.msu.su/services/malign_reduced.html). Как показывает
стандартная мера качества алгоритма построения множественного выравнивания
[3], AliBee является одним из лидеров. Несмотря на это, имеется ряд
подходов, которые его могут улучшить.
Реализация этих подходов и составляет содержание настоящей темы.
Основными этапами при построении выравнивания в алгоритме AliBee
являются: быстрые алгоритмы сравнения двух последовательностей; различные
способы кластеризации; динамическое программирование. Изучение и улучшение
каждого из этих этапов может быть содержанием для отдельной работы.
Отдельный интерес представляет сравнение работы AliBee с некоторыми
другими алгоритмами построения множественного выравнивания, например с
Multi-LAGAN [4].

[1] 1993, Biosystems, 1993, 30, 65-79б A novel method of multiple
alignment of biopolymers(MA-Tools module of GeneBee package), Brodsky L.I.,
Drachev A.L., Gorbalenya A.E., Leontovich A.M., Feranchuk S.I.
[2] Biochemistry, 1997, 62, 6, 578-582. Building multiple alignment
using iterative analyzing biopolymers structure dynamic improvement of the
initial motif alignment, Nikolaev V.K., Leontovich A.M., Drachev V.A.,
Brodsky L.I.
[3] Nucleic Acids Res. 1999 Jul 1;27(13):2682-90. A comprehensive
comparison of multiple sequence alignment programs. Thompson JD, Plewniak
F, Poch O.
Genome Res. 2003 Apr;13(4):721-31. Epub 2003 Mar 12. LAGAN and Multi-
LAGAN: efficient tools for large-scale multiple alignment of genomic DNA.
Brudno M, Do CB, Cooper GM, Kim MF, Davydov E, Green ED, Sidow A, Batzoglou
S; NISC