О ДНК-кодах

Исследуются некоторые функции сходства на множестве $q$-ичных последовательностей. Для случая $q=4$ они могут быть использованы для моделирования термодинамической энергии связи последовательностей ДНК [1, 2], что имеет ряд приложений в молекулярной биологии. На основе указанных функций сходства определяются коды, называемые ДНК-кодами [1]. Даем краткие доказательства ранее анонсированных [3], но неопубликованных результатов, связанных с известной функцией сходства выпадений [4–6]. Она равна длине наибольшей общей подпоследовательности и применяется в теории кодов, исправляющих ошибки выпадений и вставок [5]. Основной целью статьи является изучение другой функции сходства, называемой сходством блоков. Ее отличие от предыдущей заключается в том, что на подпоследовательности накладывается некоторое дополнительное условие блочности (мотивированное биологическими соображениями [2]), за счет которого не все подпоследовательности оказываются допустимыми. Получены нижние оценки на объем оптимального ДНК-кода для указанной функции сходства. Приводятся некоторые конструкции близких к оптимальным ДНК-кодов, являющихся подкодами кода с проверкой на четность для обнаружения одной ошибки в метрике Хэмминга [7].