автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Множественное выравнивание (мультиэлайнмент) для моделирования сигналов с темпоральными искажениями

Аннотация2

Введение3

1. Поиск множества соответствий между компонентами упорядоченного массива данных9

1.1. Задачи, приводящие к необходимости мультиэлайнмента сигналов9

1.1.1. Поиск периодической компоненты характеристик локомоторного аппарата человека при ходьбе11

1.1.2. Формирование общего признакового пространства в задаче распознавания образов21

1.1.3. Задача визуализации процесса эволюции гидродинамической системы23

1.1.4. Корреляционный анализ каротажных кривых26

1.2. Мультиэлайнмент белковых последовательностей28

1.3. Существующие методы мультиэлайнмента символьных последовательностей30

1.3.1. Парный разбор символьных цепочек30

1.3.1.1. Поиск разбора без минимизации неплотности36

1.3.1.2. Итерационная процедура минимизации неплотности разбора36

1.3.2. Стратегия объединяющей цепочки38

1.4. Непрерывность по оси аргумента как основная специфика сигналов44

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

2. Вариационный подход к задаче поиска соответствий на совокупности сигналов46

2.1. Структура целевой функции в задаче мультиэлайнмента сигналов46

2.1.1. Граф отношения соседства элементов упорядоченного массива данных46

2.1.2. Обобщенная целевая сепарабельная функция48

2.1.3. Стратегия консенсус-сигнала51

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

2.2. Итерационные методы оптимизации сепарабельной целевой функции59

2.2.1. Обобщенная процедура минимизации сепарабельной функции с произвольным графом смежности переменных59

2.2.2. Глобальная итерационная процедура минимизации сепарабельной функции на решетке61

2.2.3. Метод стохастической релаксации63

2.2.4. Метод моделируемого отжига64

2.3. Неитерационные методы оптимизации сепарабельной целевой функции65

2.3.1. Неитерационная процедура оптимизации сепарабельной функции с решетчатой смежностью переменных65

2.3.2. Оптимизация сепарабельной функции с древовидной смежностью переменных67

2.3.2.1. Структура целевой сепарабельной функции с древовидной смежностью переменных67

2.3.2.2. Функция Беллмана и основная процедура оптимизации 69

2.3.2.3. Маргинальная узловая функция72

2.3.3. Оптимизация сепарабельной функции со смежностью переменных в виде цепи74

2.3.4. Применение маргинальных функций в неитерационной процедуре оптимизации76

2.4. Трудности оптимизации целевой функции в задаче мультиэлайнмента77

3. Процедуры мультиэлайнмента при малых взаимных искажениях сигналов81

3.1. Общая идея метода81

3.2. Локальная модель сигнала83

3.3. Оценивание параметров локальной модели сигнала89

3.3.1. Квадратичная локальная модель89

3.3.2. Линейная локальная модель94

3.4. Квадратичная сепарабельная целевая функция с цепочечной смежностью переменных96

3.5. Численная реализация процедуры оптимизацииS9

3.6. Результат работы процедуры112

Заключение

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

Анализ известных методов оптимизации критерия полученного вида привел к следующим выводам:

1 .итерационные методы, отличающиеся незначительной трудоемкостью, ориентированы на поиск локального экстремума, тогда как задача мультиэлайнмента является многоэкстремальной;

2.методы, нацеленные на поиск глобального экстремума функции требуют колоссального усугубления итерационного характера исследования;

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

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

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

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

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

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

1. Ахо А., Хопкрофт Дж., Ульман Дж., Построение и анализ вычислительных алгоритмов, М.: Мир, 1979.

2. Бейко И.В., Бублик Б.И., Зинько П.Н. Методы и алгоритмы решения задачоптимизации. Киев: Вища школа, 1983. - 512 с.

3. Беллман Р., Динамическое программирование. М.:ИЛ, 1960.

4. Березин И.С., Жидков И.П. Методы вычислений т.1. М.: Высшая школа, 1996.-632 с.

5. ВапникВ.Н., Червоненкис А .Я. Теория распознавания образов. М.: Наука, 1974.-415 с.

6. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. -Киев: Наукова думка, 1987. 264 с.

7. Ершов А.П. Введение в теоретическое программирование, М., Наука, 1977.

8. Кнут Д. Искусство программирования для ЭВМ. Т. 1-3, М.:Мир, 1976

9. Кормен Т., Лейзерстон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 1999. 960 с.

10. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов. 3-е изд., перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.

11. М.Б.Кривоногов, С.В.Лисицын «Применение цифровой обработки сигналов для решения задачи анализа походки человека», Известия Тульскогогосударственного университета, Серия Математика. Механика. Информатика. Том 4. Выпуск 4, Тула, 1998, стр.53-56.

12. Кристофере Н., Теория графов. Алгоритмический подход. М.:Мир, 1978.

13. Кук В., Бейз Г., Компьютерная математика, М.: Наука, 1990.

14. Кузин Л.Т. Основы кибернетики, т.1. Математические основы кибернетики. Учеб. пособие для студентов втузов. М.: Энергия, 1973. - 504 с.

15. Кулинович А.Е. Основные принципы машинной обработки каротажных кривых. В сб. Автоматическая обработка и преобразование геофизической информации. - М.: Недра, 1965,156 с.

16. В.В. Моттль, С.В.Лисицын, Ю.С.Ключарева «Компенсация темпоральных искажений (мультиэлаймент) в задачах анализа совокупностей сигналов»,

17. Всероссийская научная конференция «Современные проблемы математики, механики, информатики». Тезисы докладов, Тула, 2000, стр. 164-168.

18. В.В. Моттль, С.В. Лисицын, Ю.С. Лыкова «Процедуры мультиэлайнмента в задачах анализа массивов сигналов», Известия Тульского государственного университета, Серия Математика. Механика. Информатика. Том 6. Выпуск 3, Тула, 2000, стр. 144-150.

19. Моттль В.В., Двоенко С.Д., Середин О.С., Долгова О.В. Обучение распознаванию сигналов с учетом критерия гладкости решающего правила. -В сб. Математические методы распознавания образов. Тез. Докл. IX Всероссийской конф. М.: АЛЕВ-В, 1999. - 271 с.

20. Моттль В.В., Мучник И.Б. Лингвистический анализ экспериментальных кривых //ТИИЭР. 1979. - №5,. т. 67. - с. 28-34

21. Мучник Р.Б. Алгоритмы выделения участков кривых и их взаимного расположения. В сб. Техническая кибернетика. Материалы XX юбилейной литовской республиканской научно-технической конференции. - Каунас: Каунасский политехнический институт, 1970.

22. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2000.-304 с.

23. Основы кибернетики. Математические основы кибернетики. /Под. ред. К.А. Пупкова. Учеб. пособие для втузов. М.: Высшая школа, 1974. - 413 с.

24. Разработка алгоритмов и программ корреляции по данным геофизических исследований скважин: отчет о НИР /заключ. //ТулПИ; Научн. Руководитель В.В. Моттль. Тула, 1989. - 39 с.

25. Романовский И.В., Дискретный анализ, Невский диалект, 1999.

26. Цемель Г.И. Опознование речевых сигналов. М.: Наука, 1971. - 237 с.

27. Aho А.V., Hopcroft J.E. and Ulman J.D. The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

28. Aho A.V., Hopcroft J.E. and Ulman J.D. Data Structures and Algorithms. Addison-Wesley, 1983.

29. Baase S. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, second edition, 1988.

30. Bashford D., Chotha C., Lesk A.M. Determinants of a protein fold. Journal of molecular Biology, №196, 1987. pp. 199-216

31. Bellman R. Dynamic Programming. Princeton University Press, Princeton N.J., 1957.

32. Besag J.E. On the statistical analisis of dirty pictures (with discussion). Journal Royal Statist. Soc., В 48, 1986. pp. 259-302

33. Bondy J.A. and Murphy U.S.R. Grapth Theory with Applications. American Elsevier, 1976.

34. Brassard G. and Bratley P. Algoritthmics: Theory and Practice. Prentice-Hall, 1988.

35. Brent R.P., An improved Monte Carlo factorization algorithm. BIT, 20(2): p. 176184, 1980.

36. Cavanagh J.J.F. Digital Computer Arithmetic. McGraw-Hill, 1984.

37. Chung K.L., Elementary Probability Theory with Stochastic Processes. Springer-Verlag, 1974.

38. Connel S.D., Jain A.K. Learning Prototypes for On-Line Handwritten Digits. / 14th ICPR'98. August 16-20, 1998, Brisbane, Australia. Vol. 1. pp. 182-184

39. Cortes C., VapnikV. Support-vector networks. /Machine Learning, 1995, Vol.20, №.3.- pp. 273-297

40. Durbin R., Eddy S., Krogh A., Mitchison G. Biological sequence analysis. Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.- 356 p.

41. Drake A.W., Fundamentals of Applied Probability Theory. McGraw-Hill, 1967.

42. Horowitz E. and Sahni S., Fundamentals of Computer Algorithms. Computer Science Press, 1978.

43. Hwang K., Computer Arithmetic: Principles, Architecture and Design. John Wiley & Sons, 1979.

44. Geman S., Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans, On PAMI, Vol. 6, November 1984. pp. 721741

45. Gribskov M., McLachlan A.D., Eisenberg D. Profile analysis: detection of distantly related proteins. Roc. Nat. Acad. Sci. USA, 84, 1987. pp. 4355-4358

46. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science, 1983, 220. pp. 671-680

47. Kittler J., Foglein J. Contextual classification of multispectral pixel data. Image Vision Comput., №2, 1984. pp. 259-302

48. Knuth D.E. The Art of Computer Programming. Addison-Wesley, 1968. Second Edition 1973.

49. Manber U., Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.

50. Michael W., Whittle Gait Analysis: An Introduction. Oxford Butterworth Heinemann, 1993.

51. Mirkin В., Roberts F.S. Consensus functions and patterns in molecular sequences. Technical Report 92-37. DIMACS, Rutgers University, August, 1992.

52. Mottl V.V., Blinov A.B., Kopylov A.V., Kostin A.A. Optimisation techniques on pixels neighborhood graphs for image processing. Precceeding of the International Workshop on Graph-Based Representations. Lyon, France, April 17-18, 1997.

53. Mottl V.V., Blinov A.B., Kopylov A.V., Kostin A.A. Optimisation techniques on pixels neighborhood graphs for image processing. Graph Based Representations in Pattern Recognition. Computing, Supplement 12. Springer, 1998. pp. 135-145

54. Mottl V.V., Blinov A.B., Kopylov A.V., Zheltov S.Yu. Quasi-statistical approach to the problem of stereo image matching. Proceedings SPIE, 2363, 1994. pp. 5061

55. Mottl V., Muchnik I., BlinovA., ZabuskyN. Apparent motion in spatial time-varying data: A variational approach to point wise tracking of coherent structure in computational fluid dynamics. DIMACS Technical Report, September, 1999.

56. Mottl V., Muchnik I., Blinov A., Zabusky N. Tracking persistent structures in scientific image flows. DIMACS Technical Report, September, 1999.

57. Pincus M.A. A closed form solution of certain programming problems. Oper. Res., 1968, 16. pp. 690-694

58. Pincus M.A. Monte-Carlo metod for the approximate solution of certain types of constrained optimisation problems. Oper. Res., 1970, 18. pp. 1223-1228

59. Purdom P.W., Brown C.A. The analysis of Algorithms. Holt, Rinehart and Winston, 1985.

60. Ripley B.D. Statistics, images and pattern recognition (with discussion). Canad. J. Statist., 1986, 14.-pp. 83-111

61. SamtaneyR., SilverD., ZabuskyN., Cao J. Visualizing features and tracking their evolution. IEEE Computer, 27(7): 20-27, July 1994.

62. SedgewickR., Algorithms. Addison-Wesley, second edition, 1988.135

63. Smith A.F.M., Roberts G.O. Bayesian computation via the Gibbs sampler and related Markov Chain Monte Carlo methods. J.R. Statist. Soc.,1993, B55, №.1, pp.3-23

64. Smith R.F., Smith T.F. Pattern-induced multi-sequence aligment (PIMA) algorithm employing secondary structure-dependent gap penalties for use in comparative protein modeling. Protein Engineering, 1992, 5. pp. 35-41.

65. Strang G. Introduction to Applied Mathematics. Wellesley-Cambridge Press, 1986.

66. Taylor W.R. Identification of protein sequence homology by consensus template alignment. Journal of Molecular Biology, 1986, 188. pp. 233-258

67. Taylor W.R. A flexible method to align large numbers of biological sequences. Journal of Molecular Evolution, 1988, 28. pp. 161-169

68. TierneyL. Markov chains for exploring posterior distributions. The Annals of Statistics, 1994, Vol. 22, №4. pp. 1701-1762

69. Wang X. Visualizing and tracking features in 3D time-varying datasets. New Brunswick, New Jersey, December, 1998.

70. Wang X. Visualizing and tracking features in 3D time-varying datasets. Ph.D. Thesis. Rutgers University, 1998.