1 УДК 621.391 : 519.1 2017 г. К.Ю. Горбунов, В.А. Любецкий c ЛИНЕЙНЫЙ АЛГОРИТМ МИНИМАЛЬНОЙ ПЕРЕСТРОЙКИ СТРУКТУР1 Предлагается линейный по времени и используемой памяти алгоритм, строящий минимальную последовательность операций, которая преобразует одну структуру (ориентированный графиз циклов и цепей) в другую. <...> Структуры в такой последовательности могут иметь переменное множество ребер, список операций фиксирован и включает удаление и вставку участка структуры. <...> Приводится полное доказательство точности алгоритма, т.е. того, что он находит соответствующий минимум. <...> В работе [3] предложены операции для преобразования хромосомных структур (см. <...> В [3] приведен алгоритм вычисления числа операций в минимальной по числу операций последовательности, которая преобразует одну структуру в другую, если структуры состоят только изцепей (“линейных хромосом”); время работы алгоритма близко к линейному, явная оценка времени отсутствует. <...> В случае переменного генного состава нельзя обойтись без дополнительных операций: удаления и вставки участка особых генов, которые были предложены в [6,7]. <...> Кроме того, край исходной цепи считается склеенным с “пустым краем”; между склеенными краями общих генов двух структур может располагаться участок генов, принадлежащих только одной структуре (особые гены), 1 Исследование выполнено в ИППИ РАН за счет гранта Российского научного фонда (проект №14-50-00150). <...> В этих работах предложен линейный по времени алгоритм, строящий минимальную последовательность перестроек одной структуры в другую теми же операциями, что и в настоящей статье. <...> Авторам неизвестно, где приведено доказательство точности алгоритма из [6–8]; замечания, которые там содержатся, не позволяют его получить. <...> В работах [9–11] предлагается линейный алгоритм, основанный на пополнении обеих исходных структур особыми генами. <...> Таким образом, задача сводится к случаю равного генного состава, а суммарное число генов увеличивается <...>