Множественное выравнивание (мультиэлайнмент) для моделирования сигналов с темпоральными искажениями

Множественное выравнивание (мультиэлайнмент) для моделирования сигналов с темпоральными искажениями

Автор: Лисицын, Сергей Владимирович

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 2001

Место защиты: Тула

Количество страниц: 137 с. ил

Артикул: 2296205

Автор: Лисицын, Сергей Владимирович

Стоимость: 250 руб.

Множественное выравнивание (мультиэлайнмент) для моделирования сигналов с темпоральными искажениями  Множественное выравнивание (мультиэлайнмент) для моделирования сигналов с темпоральными искажениями 

Аннотация
В работе рассматривается ряд прикладных задач, приводящих к необходимости мультиэлайнмента сигналов анализируются проблемы, препятствующие построению эффективных процедур поиска их решения предлагается математическая постановка задачи, позволяющая преодолеть существующие проблемы в случае анализа сигналов с малыми взаимными искажениями масштаба вдоль оси аргумента в рамках вариационного подхода формируется критерий, для оптимизации которого разрабатываются высокоэффективные алгоритмы неитерационного характера.
Введение
Термин мультиэлайнмент означает результат поиска множества соответствий между сходными фрагментами нескольких анализируемых компонент, каждая из которых представляет собой массив упорядоченных данных. Поясним этот термин на примере упрощенной задачи анализа последовательностей символов из некоторого конечного алфавита, не имея в виду никакого конкретного приложения.
Пусть У А, С, Ц С конечный алфавит, из символов которого составлены цепочки разной длины АОАЛО, СОАООС, СОСО, ОСА. Нумерация цепочек произвольна, т.е. их совокупность рассматривается как неупорядоченное множество, тогда как сами цепочки являются упорядоченными последовательностями символов. Требуется восстановить множество соответствий, объединяющих одинаковые элементы различных цепочек между собой. В простейшем случае элементы цепочек можно разместить в строках таблицы, а множество соответствий между их элементами показать в форме расширенной таблицы, в которой идентичные символы находятся в одном столбце
А А А
С А
С С
1 л А А
С А
с С
С А
Термин мультиэлайнмент образовался от английского ii, что можно перевести как многомерное выравнивание. Как видно, при поиске соответствий мы анализируем одновременно несколько цепочек л осуществляем выравнивание символов последовательностей.
Задача мультиэлайнмента практически неизвестна в России. Проблема поиска множества соответствий между элементами символьных последовательностей возникла в так называемой вычислительной биохимии, где символы, обозначаемые буквами латинского алфавита, соответствуют различным аминокислотам. Каждая цепочка символов отражает первичную структуру белка, представляющего собой полимерную молекулу, образованную последовательно связанными аминокислотными остатками.
Обычно предполагается, что анализируемые последовательности образовались от одного общего белка в ходе естественных эволюционных процессов. Искажения структуры, наследуемой от белкапрародителя, могут происходить за счет пропуска, вставки или замены отдельных аминокислотных остатков. Мул ьтиэл айн мент таких цепочек дает возможность исследователю судить о том, на сколько схожи анализируемые белки, какого рода трансформации произошли в ходе развития и какова структура белкапрародителя , .
В реальных приложениях задается некая матрица сходства между элементами алфавита символов . Требуется найти мультиэлайнмент, при котором в каждом столбце результирующей таблицы, максимально допустимая длина строк которой ограниченна, стояли бы наиболее схожие, в некотором смысле, элементы. Точное решение такой задачи представляет собой значительную трудность. Тем не менее, это задача активно разрабатывается, особенно в последнее время.
В литературе описан ряд формальных постановок задачи мультиэлайнмента как задачи дискретной оптимизации. Однако эти постановки мало полезны при построении рабочих алгоритмов, поскольку приводят к полномасштабной задаче глобальной оптимизации без существенно упрощающих ограничений. Как следствие, подавляющее большинство алгоритмов основано на глубоко эвристических процедурах , , , , а алгоритмы, опирающиеся на методы глобальной оптимизации, требуют значительного усугубления итерационного характера исследования , , , .
В данной работе рассматривается аналогичная задача, но в совершенно новой постановке, позволяющей обойти проклятие перебора и построить эффективную неитерационную вычислительную процедуру. Вместо символьных цепочек анализируются сигналы разной длительности, определенные на общей, непрерывной оси некого аргумента, например, времени. Форма таких сигналов имеет существенно общие черты. Требуется определить множество соответствий, объединяющих фрагменты различных сигналов со сходной локальной формой. Это позволило заимствовать типичный для области белковой инженерии термин и сформулировать новую постановку непрерывной задачи мультиэлайнмента применительно к сигналам.
Актуальность


Во второй главе рассматривается вариационный подход к решению поставленной задачи формируется обобщенный критерий оптимизации в виде целевой сепарабельной функции приводится обзор существующих итерационных методов оптимизации полученного критерия раскрывается сущность подхода к построению оптимизационной процедуры неитерционного характера анализируется специфика задачи мультиэлайнмента, порождающая комплекс проблем, затрудняющих возможность применения известных методов оптимизации. В третьей главе излагается способ устранения возникших проблем посредством оригинальной формулировки задачи, позволяющей свести многоэкстремальный критерий оптимизации к критерию квадратичного вида, а также использовать неитерационный метод поиска решения описывается общая схема алгоритмов, отражающих две возможные модификации процедуры, и выводятся основные рекуррентные соотношения, необходимые для численной реализации процедуры анализируются результаты экспериментов. В настоящее время компьютерная техника находит свое применение в различных областях человеческой деятельности. Растет доля многопользовательских компьютерных систем и систем работающих в режиме реального времени. В то же время возрастает поток информации обрабатываемой с помощью компьютеров. В связи с этим возникает необходимость в разработке новых эффективных алгоритмов обработки данных сложной структуры. Теории разработки компьютерных алгоритмов посвящена обширная литература, например 7, 9. Отдельно можно выделить работы посвященные методам анализа эффективности алгоритмов , , , и их надежности , , , . Данная работа посвящена построению и анализу практического применения нового эффективного алгоритма анализа сигналов. Сигналом называют данные, представляющие собой числовую последовательность, упорядоченную вдоль оси одного или нескольких аргументов, например, по времени, частоте или пространственной координате. На практике, как правило, приходится иметь дело с набором сигналов различной длины, каждый из которых подвержен индивидуальным искажениям масштаба вдоль оси аргумента в виде локальных растяжений или сжатий рис. Наиболее ярким примером такого набора сигналов является результат многократного измерения какоголибо физического процесса. Этот же тип искажений характерен для квазипериодических сигналов, получаемых в результате измерений биомеханических параметров, например, углов сгиба конечностей при ходьбе человека. Здесь темпоральные искажения обусловлены непостоянством темпа ходьбы, который может изменяться от шага к шагу. В сигналах, образованных числовыми характеристиками аминокислотных остатков, образующих полимерные молекулы белков, локальные искажения масштаба вдоль оси аргумента появляются изза пропусков, вставок или замены отдельных аминокислот в родственных белках, произошедших различным образом от общего прародителя в ходе эволюции , . Поиск периодической компоненты характеристик локомоторного аппарата человека при ходьбе является одной из наиболее важных задач при анализе походки человека в целом. Как будет показано в дальнейшем, поиск периодической компоненты непосредственно приводит к задаче мультиэлайнмента. История анализа походки имеет солидную историю, начиная с ранних описательных исследований, через использование чрезвычайно хитроумных методов измерения, до научного анализа, статистических исследований и математического моделирования процессов ходьбы. Очень бурно эта область развивается в последние три десятилетия, за это время было опубликовано несколько сот работ по этому предмету. Несомненно, походка наблюдалась с тех пор как человек начал эволюционировать, по первый систематический анализ этого предмета дошел до нашего времени из эпохи Ренессанса, когда Леонардо Да Винчи, Галилей и Ньютон все сделали описания процесса ходьбы. Самос раннее сообщение, использующее точный научный метод . Эе МоШ Апппа1игтГ, опубликованной в году Джованни Борелли, который работал в Италии и был студентом Галилея. Джованни Борелли измерил центр тяжести тела, и описал, как поддерживается баланс при ходьбе с постоянным перемещением вперед области опоры предусмотренной ногами. Братья Вебер в Германии дали первое ясное описание цикла походки в году. В м году ЭтьеннЖюль Марей, работавший в Париже, опубликовал анализ перемещений человеческих конечностей.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.252, запросов: 244