NEU-2002

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

При решении задачи восстановления утерянных данных существенным является вопрос о представленности алфавита в той части последовательности, которая доступна исследователю: если алфавит заранее не известен, и утерянным оказался некоторый символ (либо набор символов), не встречающийся в наблюдаемой части последовательности, то такую утрату следует считать невосстановимой никакими методами.

Пусть алфавит известен заранее ({A,C,G,T}). Пусть, далее, имеется последовательность длины N, содержащая лакуну длины L, так, что N=N₁+L+N₂, где N₁ и N₂ — два фрагмента, имеющиеся в распоряжении исследователя. Общий подход к заполнению этой лакуны заключается в следующем: будем заполнять её копиями (малых) подпоследовательностей (слов) из имеющихся в распоряжении фрагментов так, чтобы получившаяся после заполнения последовательность была в том или ином смысле подобна исходной в наибольшей степени. Сформулируем способ заполнения и критерий подобия точнее [1].

По имеющимся в распоряжении исследователя фрагментам исходной последовательности составим частотный словарь (множество всех слов — подпоследовательностей заданной длины q — с указанием их частот); такой частотный словарь будем называть опорным. Будем заполнять лакуну словами из него. Задача заполнения сводится к построению слова длины L+2s символов, 0≤s<q, где первые и последние s символов должны совпадать с s последними (первыми, соответственно) s символами фрагментов последовательности, ограничивающих собственно лакуну. Эти s символов называются опорой. Если такое заполнение существует и единственно, то задача считается решённой. Если такое заполнение существует и не единственно, то среди всех возможных заполнений выберем то, которое обеспечивает максимум энтропии пополненного частотного словаря. Пополненным будем называть словарь, построенный по всей последовательности целиком, после заполнения в ней лакуны. Если заполнение из универсального словаря не существует, то будем заполнять лакуну любыми мыслимыми словами (той же длины), возможными в исходном алфавите. Среди всех возможных замощений лакуны выберем в качестве заполнения то, для которого условная энтропия опорного частотного словаря относительно пополненного (в результате заполнения лакуны) окажется минимальным. Оба критерия обеспечивают минимум дополнительной, привносимой в заполняемую последовательность информации.

Алгоритмы заполнения лакуны в собственном смысле в последовательности сводятся к перебору всех возможных вариантов; данная задача является алгоритмически неразрешимой [3, 4]. В связи с этим указанная задача решалась с помощью программного имитатора (на машине фон Неймановского типа) идеального высоко параллельного вычислительного устройства — кинетической машины Кирдина [2 – 4]. С целью повышения эффективности вычислений стандартная модель КМК была видоизменена: была существенно повышена “концентрация” тех слов, которые являются продолжениями опоры, а “концентрация” слов, не являющихся такими продолжениями — существенно снижена. Вычислительные эксперименты проводились на модельной последовательности, представляющей собой фрагмент полного генома бактериофага длиной 20060 символов.

Численный эксперимент состоял из следующих этапов: составления опорного словаря, построения заполнения лакуны и выбора среди всех заполнений оптимального. В каждой сессии эксперимента в КМК помещалось 1000 затравок (опор), которые затем продолжались (вправо, для определённости). При этом частоты слов в опорном словаре не изменялись. Среди заполнений, получающихся из исходного набора затравок, лишь небольшая часть соответствует длине лакуны; большая часть оказывается как правило короче. Для повышения эффективности работы модифицированной КМК вся лакуна разбивалась на n частей (n = 2, 3 либо 4), в которых все заполнения, прекратившие свой рост до соответствующей длины, уничтожались, а число тех, которые доросли, увеличивалось в m раз (m = 2, 3 либо 4). Существование оптимального заполнения устанавливалось эмпирически: либо КМК строила хотя бы одно заполнение, либо вопрос о его существовании оставался открытым. Во всех экспериментах длина опоры выбиралась равной q – 1, где q — толщина опорного словаря.

Проведённые вычислительные эксперименты показали, что для использованной символьной последовательности и словарей толщины от 3 до 8 всегда существует заполнение по опорному частотному словарю. Было также обнаружено существование критической толщины словаря (равной 6). Для словарей меньшей толщины энтропия частотного словаря восстановленной последовательности всегда была больше энтропии частотного словаря исходной, а для словарей большей толщины — меньше. Для критической толщины поведение энтропии частотного словаря восстановленной последовательности носило нерегулярный характер. Вычислялись также значения условной энтропии; наиболее близкие к 0 значения наблюдались для словарей толщины 4 и 5.

1.  Садовский М.Г. Восстановление пробелов в символьных последовательностях по наблюдаемым информационным характеристикам // 7 Всерос.конференция “Нейроинформатика и её приложения”, Красноярск 1 – 3 октября 1999 г. С.129.;

2.  Kirdin A.N. Ideal ensemble model of parallel computations // Neural informatics and its applications. Krasnoyarsk, KGTU, 1997. p.101.;

3.  Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: Kinetic Model of Structureless Parallelism. Advances in Modelling & Analisis. AMSE, V.5, No5, 2000.;

4.  Gorban A.N., Gorbunova K.O., Wunsch D.C. Liquid Brain: The Proof of Algorithmic Universality of Quasichemical Model of Fine-Grained Parallelism. Neural Network World 4/2001, p.391 – 412.