Материал: Учебное пособие Немирко Манило

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

1,9.

Таким образом, оптимальной стратегией врача будет следующая. Если в первый день состояние больного оценено на 3, то в этот день проводится операция. В случае же, если в первый день состояние больного оценивается меньше, чем на 3, решение об операции откладывается до следующего дня. Если на второй день состояние больного оценивается на 3 или на 2, то в этот день проводится операция. Если на второй день состояние больного оценено на 1, то операция откладывается на 3-й день. При такой тактике мы рассчитываем, что в момент операции состояние больного в среднем окажется равным 2,336 (вместо 1,9 при чисто случайной тактике).

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

2.4. Выравнивание символьных последовательностей

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

56

(эталонной) цепочки T2 , т. е. делают их длины равными. Оно обеспечивает

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

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

Пусть необходимо выровнять две упорядоченные последовательности символов T1 и T2 . Вначале паре сравниваемых цепочек T1, T2 сопоставим

сеть G (T1, T2 ), которая строится следующим образом [15].

Составим прямоугольную решетку, столбцы которой соответствуют символам первой цепочки T1, а строки – символам второй цепочки T2 . Каж-

дая клетка этой решетки – квадрат с ребром единичной длины. Клеткам сопоставлены упорядоченные пары индексов, указывающие место соответствующих ей символов в цепочках: клетке (i, j) соответствует i -й по поряд-

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

Множество всех вершин такой решетки есть множество вершин графа сети G (T1, T2 ), число их равно q = (m +1)(n +1), где m – число символов в T1, n – число символов в T2 , а множество всех построенных и ориентированных ребер – множество дуг этого графа. Истоком S0 сети является самая левая верхняя вершина, а стоком Sk – самая правая нижняя вершина.

57

Пусть T1 = a a a b b c a a и T2 = a a b c b, тогда соответствующая этой паре цепочек сеть G (T1, T2 ) задается в виде рис. 2.17. Каждый путь S , ведущий из истока S0 в сток Sk сети G (T1, T2 ), порождает цепочку элементарных трансформаций, переводящую T1 в T2 . При этом движение по левой вертикали клетки (i, j) означает, что между последним символом уже трансформированной части цепочки T1 и первым символом еще не трансформированной ее части (им, очевидно, является символ, стоящий в T1 на i -м месте) вставляется символ, стоящий в T2 на j -м месте. Движение по верхней горизонтали этой клетки означает, что в T1 требуется удалить символ, стоящий на i -м месте. Наконец, движение по диагонали означает, что символ, стоящий в T1 на i -м месте, остается в выстраиваемой цепочке без изменений.

Зададим на множестве дуг сети G (T1, T2 ) систему весов: каждой вертикальной и горизонтальной дуге припишем вес 1, а каждой диагональной дуге припишем вес 0. Длину пути l (S), как обычно, определим как сумму весов

дуг, лежащих на этом пути.

Представленная в виде ориентированного графа сеть (рис. 2.17) показывает множество Φ(T1, T2 ) всех трансформаций цепочки T1 = a a a b b c a a

58

в T2 = a a b c b. Как видно из рисунка, входную S0 и выходную Sk вершины полученного графа связывают только те пути, по которым цепочка T2 может быть получена из T1 в соответствии с возможными последователь-

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

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

чайшего пути из множества путей Φ(T1, T2 ):

r (T1, T2 )= min( )l (S).

SΦ T1,T2

Задача нахождения кратчайшего пути может быть решена с использованием метода динамического программирования.

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

Выравниванием слов U = u1, u2, , um и V = v1, v2, , vn будем называть пару U и V длины l ≥ max (m,n), где слова U и V получаются из исходных слов U и V в результате элементарных преобразований таким образом, чтобы в обоих словах U и V не было пустых символов в одинаковых позициях. При этом в общем случае могут быть использованы следующие операции редактирования (трансформации): замена, удаление и вставка символа.

Пусть для любой пары символов α, β определена положительная стоимость δ(α→β) замены α на β. Введение пустого символа ε позволяет све-

сти операции удаления и добавления к операции замены. В частности, замена α→ ε соответствует удалению α, а ε →β – вставке β.

l

W (U, V )= ∑δ(ui → vi ).

i=1

Тогда каждое выравнивание получает свою цену. Стоимость выравнивания пустых строк полагают равной нулю.

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

Суть процедуры выравнивания заключена в вычислении стоимости оптимального выравнивания между всевозможными начальными фрагментами (префиксами) двух сравниваемых слов U и V . При этом задачу нужно р е- шать в порядке возрастания длин фрагментов, благодаря чему на каждом шаге выравнивания (i , j ) будет известна стоимость оптимального выравнивания между префиксами меньшей длины. Оптимальное выравнивание между префиксами длины i и j может быть построено одним из трех способов:

1) сопоставлением префиксов длины (i −1) и ( j −1), а также символов ui и v j . Этот случай соответствует оставлению символов ui и v j в выравниваемых словах;

2)сопоставлением префикса длины (i −1) с префиксом длины j , а так-

же символа ui с пустым символом ε. Данный случай соответствует удалению символа ui ;

3)сопоставлением префикса длины i с префиксом длины ( j −1), а также пустого символа ε с символом v j . Данный случай соответствует вставке

символа v j .

Легко видеть, что поскольку оптимальные выравнивания для префиксов меньших длин уже построены, то вышеприведенные правила позволяют его построить и для префиксов длины i и j .

60