Сметанин Ю. Г., Ульянов М. В.
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов

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

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

PDF

Бібліографічний опис:
Сметанин Ю. Г., Ульянов М. В. Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов. Кибернетика и системный анализ. 2014. Т. 50, № 1. С. 168-177. URL: http://jnas.nbuv.gov.ua/article/UJRN-0001314652