ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МУЛЬТИЭВРИСТИЧЕСКОГО ПОДХОДА В ЗАДАЧЕ СРАВНЕНИЯ ГЕНЕТИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

  • Борис Феликсович Мельников Тольяттинский государственный университет
  • Александр Геннадьевич Панин Тольяттинский государственный университет
Ключевые слова: мультиэвристический подход, анализ генетических последовательностей, расстояние Левенштейна, выравнивание строк, параллельное программирование

Аннотация

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

Литература

1. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. – СПб: Невский Диалект, БХВ-Петербург. – 2003.
2. Б. Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ(НАН Украины), 2006, №3. – С.32–42.
3. Б.Ф. Мельников. Эвристики в программировании недетерминированных игр. // Известия РАН. Программирование, 2001, № 5. – С. 63–80.
4. А. Панин. Применение мультиэвристического подхода к задаче определения схожести ДНК. // Вектор науки ТГУ №3(17). – Тольятти, 2011. – стр. 27-29.
5. S. Henikoff, J.G. Henikoff. Amino Acid Substitution Matrices from Protein Blocks. // PNAS 89(22), 1992. – p. 10915–10919.
6. D.S. Hirschberg. A linear space algorithm for computing maximal common subsequences. // Communications of the ACM 18(6), 1975. – p. 341–343.
7. J.W. Hunt, T.G. Szymanski. A fast algorithm for computing longest common subsequences. // Communications of the ACM, Vol. 20, No. 5, 1977. – p. 350–353.
8. B. Melnikov, A. Radionov, V. Gumayunov. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Systems(ICEIS-2006), Pathos(Cyprus) – pp. 91–95;
9. E.W. Myers. An Overview of Sequence Comparison Algorithms in Molecular Biology. – 1991.
10. S. Needleman, C. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins // Journal of Molecular Biology, 1970, 48(3). – p. 443–453.
11. A. Shipunov. Systema Naturae or the outline of living world classification // Protistology. 2009. 6(1). – p. 3–13
12. I. Torshin. Bioinformatics in the Post–Genomic Era: The Role of Bio-physics, – Novapublishers, 2006
13. R.A. Wagner, M.J. Fischer. The string-to-string correction problem. // Journal of the ACM, Vol. 21, No. 1, 1974. – p. 168–173.
14. G. Wieds. Bioinformatics explained: BLAST versus Smith-Waterman. –CLCBio, 2007.
15. A. C. Wilson, R. L. Cann, S. M. Carr, M. George Jr., U. B. Gyllensten, K. Helm-Bychowski, R. G. Higuchi, S. R. Palumbi, E. M. Prager, R. D. Sage, and M. Stoneking. Mitochondrial DNA and two perspectives on evolutionary genetics. // Biological Journal of the Linnean Society(1985) 26. – p. 375–400.
NCBI Nucleotide database – [URL] http://www.ncbi.nlm.nih.gov/nuccore (дата обращения 29.09.2012)
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)