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

  Повний текст PDF - 123.358 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"