О некоторых алгоритмах работы с длинными строками и их применении в задачах дискретной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Панин, Александр Геннадьевич

• Панин, Александр Геннадьевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Панин, Александр Геннадьевич

Глава 1. Введение.

1.1 Основные задачи исследования.

1.2 Научная новизна.

1.3 Краткое содержание работы.

Глава 2. Фундаментальные понятия предметной области.

2.1 Эвристические алгоритмы.

2.2 Вейвлет-анализ.

2.3 Кластеризация.

2.4 Генетические алгоритмы.

2.5 Задачи обработки строк.

Глава 3. Мультиэвристический подход в задаче сравнения сигналов акустической эмиссии.

3.1 Математическая модель сигнала.

3.2 Предварительная обработка сигналов.

3.2.1 Выделение импульсов акустической эмиссии.

3.2.2 Вейвлет-преобразование сигналов.

3.2.3 Особенности применения технологии NVIDIA CUD А.

3.3 Сравнение сигналов.

3.3.1 Использование мультиэвристического подхода.

3.3.2 Функция корреляции.

3.3.3 Специальная версия алгоритма вычисления расстояния Лёвенштейна для сравнения сигналов.

3.3.4 Ещё один способ задания признаков.

3.4 Кластеризация.

3.5 Оптимизация параметров алгоритма.

3.5.1 Генетический алгоритм.

3.5.2 Метод Брента.33 •

3.5.3 Параметры оптимизации.

3.6 Результаты кластеризации.

Глава 4. Мультиэвристический подход в задаче сравнения генетических последовательностей.

4.1 Математическая модель ДНК.

4.2 Реализация мультиэвристического подхода.

4.3 Алгоритм поиска наибольшей общей подпоследователности.

4.4 Алгоритм Нидлмана-Вунша.

4.5 Результат сравнения цепочек ДНК.

Глава 5. Алгоритм поиска наибольшей общей подпоследовательности.

5.1 Математическая постановка задачи.

5.2 Описание нового алгоритма.

5.2.1 Изменение порядка перебора ячеек матрицы.

5.2.2 Использование массивов длин префиксов.

5.2.3 Использование списков вхождения символов.

5.3 Некоторые свойства алгоритма.

5.4 Схема алгоритма.

5.5 Оценка сложности.

5.6 Тестирование алгоритма.

Глава 6. Аппроксимационный алгоритм поиска наибольшей общей подпоследовательности.

6.1 Описание алгоритма.

6.2 Тестирование алгоритма.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Панин, Александр Геннадьевич

Основные результаты работы заключаются в следующем:

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

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

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

4. Разработан алгоритм неточного поиска наибольшей общей подпоследовательности. Алгоритм работает за линейное время для двух строк с точностью порядка 0.98 (для фрагментов ДНК длиной 1 миллион символов). В общем случае, для к строк, сложность так же является линейной относительно длин строк.

5. Проведён анализ эффективности разработанных алгоритмов.

Предметный указатель алгоритм

Апостолико и Гиерра 48 Вагнера-Фишера 42, 48 Машека и Патерсона 49 нечёткой кластеризации 28 Нидлмана-Вунша 42 поиска наибольшей общей подпоследовательности 49 приближённый 59 Ханта-Шиманского 48 Хиршберга 48 вейвлет 10 вейвлет-преобразование 10, 20 генетический алгоритм 11, 30 импульсы акустической эмиссии 18 кластеризация 11,28 метод акустической эмиссии 16 Брента 32 митохондриальная ДНК 43 мультиэвристический подход 9, 24,39 наибольшая общая подпоследовательность 14, 47 оператор естественного отбора 11,12 мутации 11, 12 скрещивания 11, 12, 31 подпоследовательность 14 пропорциональный отбор 13 расстояние Лёвенштейна 14 для сигналов 26 редакционное расстояние 14 предписание 14 рулеточный отбор 13 турнирный отбор 13 фитнес-функция 12 функция корреляции 26 эвристика 9 эвристические алгоритмы 9 NVIDIA CUDA 22

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Панин, Александр Геннадьевич, 2011 год

1. А. Аграновский, Д. Леднов. Теоретические аспекты алгоритмов обработки и классификации речевых сигналов — Москва: Радио и связь, 2004. — 164 с.

2. Д.А. Александров. Алгоритм муравьиной колонии для задачи о минимальном, покрытии. // XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, тЗ(1998), Иркутск. — с. 17—20.

3. М. Алёхина, А. Лысенко, Б. Мельников. Об одном подходе к моделированию вычислительных устройств. // Известия вузов. Поволжский регион. Физико-математические науки. No.2, 2007. — С.2—9;

4. Н.М. Астафьева. Вейвлет-анализ: основы теории и примеры применения// Успехи физических наук,1996, №11(166) — Москва: Издательство Института космических исследований РАН, 1996— с. 1145—1170(1996)

5. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. // Москва: Вильяме, 2003. — 382 с.

6. A.A. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод. Методы и модели анализа данных: OLAP и Data Mining — Санкт-Петербург: БХВ-Петербург, 2004. 336 с.

7. С. Баумгертнер, Б. Мельников. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов // Вестник Воронежского гос. унив., сер. Сист. анализ и инф. техн., 2010, № 1. — С.5-7;

8. A.B. Боресков, A.A. Харламов. Основы работы с технологией CUDA. — М.: ДМК Пресс, 2010. 232 е.: ил.

9. И. Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА, 1997. - 112с.

10. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. — СПб: Невский Диалект, БХВ-Петербург. 2003.

11. E.H. Гончаров, Ю.А. Кочетов. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. // Дискретный анализ и исследование операций. Сер. 2. тб(1999); №4. — с. 12-32.

12. JI.E. Горбачевская, Ю.А. Кочетов. Вероятностная эвристика для двухуровневой задачи размещения. // XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1(1998), Иркутск. с. 249-252.

13. Ю. Громкович. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. БХВ-Петербург, 2010. - 336 с.

14. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Издательство «Мир», 1982. - 416 с.

15. И. Добеши. Десять лекций по вейвлетам. — Ижевск: Издательство НИЦ «Регулярная и хаотическая динамика», 2001. — 464 с.

16. Н.Г. 3агоруйко. Прикладные методы анализа данных и знаний. — Новосибирск: .ИМ СО РАН, 1999.

17. С. Исаев Генетические алгоритмы в задачах оптимизации. / 2005. URL: http://masters.donntu.edu.ua/2005/kita/shestopalov/library/gaoptim.htm(AaTa обращения 29.10.2011)

18. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. -М.: Вильяме, 2005. 1296 с.

19. Д. Кнут. Искусство программирования, т.2. Получисленные алгоритмы. — Москва: Вильяме, 2007. — 832 е.

20. К. Крашенинникова, А. Панин Об одном подходе к кластеризации ситуаций при решении переборных задач // В кн.: «Некоторые вопросы математического моделирования дискретных систем», монография. — Тольятти: изд-во ТГУ, 2011.

21. В.М. Курейчик. Генетические алгоритмы. — Таганрог: изд-во ТРТУ, 1998. -242 с. '

22. Медиченко М.П., Литвинов В.П. Радиотехнические цепи и сигналы. Ч. 1. -М.: МГОУ, 2011.-120 с.

23. Б. Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ(НАН Украины), 2006, №3. — С.32-42.

24. Б.Ф. Мельников. Эвристики в программировании недетерминированных игр. // Известия РАН. Программирование, 2001, № 5. — С. 63-80.

25. Б. Мельников, Е. Мельникова. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации. // Известия вузов. Поволжский регион. Технические науки. № 2, 2008. С.23-28;

26. Б. Ф. Мельников, А. Н. Радионов. О выборе стратегии в недетерминированных антагонистических играх. // Известия РАН. Программирование, 1998, №5.-С. 55-62.

27. Б. Мельников, С. Эйрих. Подход к комбинированию незавершённого метода ветвей и границ и алгоритма имитационной нормализации // Вестник

28. Воронежского гос. ун-та, сер. Сист. анализ и инф. техн., 2010, № 1, — С.35-38.

29. Е. Мельникова. Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации: дисс. . : канд. физ.-мат. наук : 05.13.18 // Тольятти, ТГУ, 2009. 152 с.

30. Мерсон, Д. Л. Оценка состояния образцов стали 20 по параметрам акустической эмиссии / Д. Л. Мерсон, Е. В. Черняева, Д. Е. Мещеряков // XVII Петербургские чтения по проблемам прочности. Сборник материалов. СПб.: СПбГУ, 2007. Ч. 1 - С. 78-81.

31. Д. Рутковская, М. Пилиньский, Л. Рутковский Нейронные сети, генетические алгоритмы и нечёткие системы — 2-е изд. — М.: Горячая линия-Телеком, 2008.-С. 452

32. Ю. Сато. Обработка сигналов. Первое знакомство. Москва: Додека, 2000.- 175 с.

33. М. Сингер, П. Берг. Гены и геномы. Том 1. — М.: Мир, 1998. 373 с.

34. У. Смит Методы и алгоритмы вычислений на строках. М.: ООО «И.Д. Вильяме», 2006. - 496 с.

35. Л.Н. Степанова, А.Е. Кареев. Использование кластерного анализа для определения связи сигнала акустической эмиссии с характером разрушения в металлических образцах // Контроль. Диагностика. 2005. — №9. — С. 18-23.

36. А. Шевченко. Скважинная сейсморазведка. — Москва: Изд-во Российского государственного университета нефти и газа им. Губкина, 2002. 129c.

37. A. Apostolico, C. Guerra. The longest common subsequence problem revisited. // Algorithmica, Vol. 2, 1987. p. 315-36.

38. R. Bellman, S. Dreyfus. Applied Dynamic Programming Princeton University Press, Princeton NJ, 1962.

39. L. Bergroth, H. Hakonen, T. Raita. A Survey of Longest Common Subsequence Algorithms. // Proceedings of SPIRE, 2000. p. 39-48.

40. K.D. Boese, A.B. Kahng, S. Muddu. A new adaptive multi-start technique for combinatorial global optimizations. // Oper. Res. Lett. vl6(1994), N2. — p. 101-114.

41. R. Brent. Algorithms for Minimization without Derivatives, Chapter 4. // Prentice-Hall, Englewood Cliffs, NJ, 1973.

42. K. Deb, A. Kumar. Real-coded* genetic algorithms with simulated binary crossover. // Studies on multi-modal and multi-objective problems. — Complex Systems, 9(6), 1995. p. 431-454.

43. G. Gönnet, R. Scholl. Scientific Computation. Cambridge University Press, 2009.-250 p.

44. A.S. Graham. String Search. // Technical Report TR-92-gas-01. School, of Electronic Engineering Science University College of North Wales. — 1992.

45. A.S. Graham. String Searching Algorithms. World Scientific, 1994.

46. S. Henikoff, J.G. Henikoff. Amino Acid Substitution Matrices from Protein Blocks. //PNAS 89(22), 1992. -p. 10915-10919.

47. D.S. Hirschberg. A linear space algorithm for computing maximal common subsequences. // Communications of the ACM 18(6), 1975. p. 341-343.

48. J.W. Hunt, T.G. Szymanski. A fast algorithm for computing longest common subsequences. // Communications of the ACM, Vol. 20, No. 5, 1977. p. 350353.

49. S. Kirkpatrick, G. Toulouse. Configuration space analysis of traveling salesman problems. // J. de Phys. v46(1985), p. 1277-1292.

50. W.J. Masek, M.S. Paterson. A faster algorithm for computing string-edit distances. // Journal of Computer and Systems Sciences, Vol. 20, No. 1, 1980. — p. 18-31.

51. W.J. Masek, M.S. Paterson. How to compute string-edit distances quickly. // Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. D.Sankoff, J.B.Kruskal eds. Addison-Wesley, 1983. -p. 337-349.

52. B. Melnikov, A. Radionov, V. Gumayunov. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Sys-tems(ICEIS-2006), Pathos(Cyprus) pp. 91-95;

53. D. Merson, S. Dement'ev, A. Ioffe, P. Suvorov, A. Vinogradov. Acoustic Emission during Hydrogen Charging1 of a Pipeline Steel // ISIJ International , Vol. 51(2011) , No. 10. The Iron and Steel Institute of Japan, 2011 -pp. 1682-1687.

54. M. Mitchell. An Introduction to Genetic Algorithms. Cambridge, MA: The MIT Press, 1996.

55. H. Muhlenbein. Parallel genetic algorithm, population dynamics and combinatorial optimization. // Proc. Third Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989.-p 416-421.

56. E.W. Myers. An Overview of Sequence Comparison Algorithms in Molecular Biology.-1991.

57. 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.

58. A. Pollock Acoustic Emission Inspection // Metals Handbook, Ninth Edition ASM International. Vol. 17.1989.-P.278-294.

59. A. Shipunov. Systema Naturae or the outline of living world classification //

60. Protistology. 2009. 6(1). p. 3-13

61. G. Stephen. String Search Algorithms World Scientific, 1994. - 256 p.

62. I. Torshin. Bioinformatics in the Post-Genomic Era: The Role of Bio-physics, Novapublishers, 2006

63. R.A. Wagner, M.J. Fischer. The string-to-string correction problem. // Journal of the ACM, Vol. 21, No. 1, 1974.-p. 168-173.

64. G. Wieds. Bioinformatics explained: BLAST versus Smith-Waterman. — CLCBio, 2007.

65. ГОСТ 27655-88. Акустическая эмиссия. Термины, определения и обозначения. — М.: Издательство стандартов, 1988. — 29 с.

66. Библиотека ALGLIB — URL. http://alglib.sources.ru/ (дата обращения 29.10.2011)

67. Генетические алгоритмы. — URL.: , http://math.nsc.ru/AP/benchmarks/UFLP/uflpga.html (дата обращения 29.10.2011)

68. NCBI Nucleotide database URL. http: //www.ncbi.nlm.nih.gov/nuccore (дата обращения 29.10.2011)

69. Processors Intel® microprocessor export compliance metrics // URL.:http://www.intel.com/support/processors/sb/cs-02314 3.htm (дата обращения: 29.10.2011)