<p>Введение. Задача о наименьшей общей надстроке имеет множество применений в<br /> задачах вычислительной биологии (например, в сборке генома [1]). Задача является NP-<br /> трудной [2], однако известны различные эвристические алгоритмы, позволяющие получать<br /> приемлемые по оптимальности решения. Для одного из этих алгоритмов (GREEDY [3])<br /> имеется следующая теоретическая оценка оптимальности: длина надстроки, полученной<br /> этим алгоритмом, не может превышать 3,5N, где N – длина наименьшей надстроки [4].<br /> Однако неизвестны входные данные, где длина такой надстроки равняется или превышает<br /> 2N.<br /> Построение сложных тестовых данных для задачи о наименьшей общей надстроке, как<br /> правило, производится вручную. В работе предлагается подход к построению таких тестовых<br /> данных с помощью эволюционных алгоритмов. Вводятся новые критерии качества тестовых<br /> данных. Тесты, сгенерированные с помощью эволюционного алгоритма, по указанным<br /> критериям превосходят известные тесты, построенные вручную.</p>