4551
правка
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями
Материал из WEGA
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок (посмотреть исходный код)
Версия от 15:05, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Выравнивание нескольких строк; глобальная задача выравнивания нескольких строк == Постановка задачи == Множественное выравнивание последовательностей является важной задачей вычислительной биологии. Она применяется в т...») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 75: | Строка 75: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
В работе приводятся два эксперимента, показывающие, что границы ошибки в теоремах 1 и 2 для меры SP в наихудшем случае являются пессимистичными по сравнению с типичной ситуацией, возникающей на практике. | В работе приводятся два эксперимента, показывающие, что границы ошибки в теоремах 1 и 2 для меры SP в наихудшем случае являются пессимистичными по сравнению с типичной ситуацией, возникающей на практике. | ||
В экспериментах использовалась следующая схема оценки: s(a; b) = 0, если a = b;s(a; b) = 1, если либо a, либо b – пробел; в противном случае s(a; b) = 2. Поскольку было показано, что вычисление оптимального множественного выравнивания с минимальной оценкой SP является NP-трудной задачей, авторы оценивают эффективность своих алгоритмов, используя нижнюю границу P i < j D(Xi ; Xj) (напомним, что D(Xi;Xj) – это оценка оптимального парного выравнивания Xi и Xj). Было выровнено 19 сходных аминокислотных последовательностей со средней длиной 60 гомеобоксов от разных видов. Отношение оценок, полученных при выравнивании методом центральной звезды, к нижней границе составляет всего 1,018, что далеко от наихудшей границы ошибки, указанной в Теореме 1. Также было проведено выравнивание 10 не очень похожих последовательностей вблизи гомеобоксов, для которых отношение оценок выравнивания к нижней границе составило 1,162. Результаты также показывают, что выравнивание, полученное с помощью рандомизированного алгоритма, обычно не слишком далеко от нижней границы. | |||
== См. также == | |||
* [[Статистическое множественное выравнивание]] | |||
== Литература == | |||
1. Bafna, V., Lawler, E.L., Pevzner, P.A.: Approximation algorithms for multiple sequence alignment. Theor. Comput. Sci. 182, 233-244(1997) | |||
2. Francis, Y.L., Chin, N.L.H., Lam, T.W., Prudence, W.H.W.: Efficient constrained multiple sequence alignment with performance guarantee. J. Bioinform. Comput. Biol. 3(1), 1 -18 (2005) | |||
3. Dalli, D., Wilm, A., Mainz, I., Stegar, G.: STRAL: progressive alignment of non-coding RNA using base pairing probability vectors in quadratic time. Bioinformatics 22(13), 1593-1599 (2006) | |||
4. Elias, I.: Setting the intractability of multiple alignment. In: Proc. of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), 2003, pp. 352-363 | |||
5. Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull. Math. Biol. 55(1), 141-154(1993) | |||
6. Pevsner, J.: Bioinformatics and functional genomics. Wiley, New York (2003) | |||
7. Pevzner, P.A.: Multiple alignment, communication cost, and graph matching. SIAM J. Appl. Math. 52,1763-1779 (1992) | |||
8. Pevzner, P.A.: Computational molecular biology: an algorithmic approach. MIT Press, Cambridge, MA (2000) | |||
9. Tang, C.Y., Lu,C.L., Chang, M.D.T.,Tsai,Y.T., Sun,Y.J.,Chao, K.M., Chang, J.M., Chiou, Y.H., Wu, C.M., Chang, H.T., Chou, W.I.: Constrained multiple sequence alignment tool development and its application to RNase family alignment. In: Proc. of the First IEEE Computer Society Bioinformatics Conference (CSB 2002), 2002, pp. 127-137 | |||
10. Tompa, M.: Lecture notes. Department of Computer Science & Engineering, University of Washington. http://www.cs.washington.edu/education/courses/527/00wi/. (2000) | |||
11. Wang, L. Jiang, T.: On the complexity of multiple sequence alignment. J. Comp. Biol. 1,337-48 (1994) | |||
