Эта публикация цитируется в
4 статьях
Теория кодирования
О максимальном числе различимых строк под действием коротких тандемных дупликаций
М. Ковачевич Факультет технических наук, Университет г. Нови-Сад, Сербия
Аннотация:
Множество всех
$q$-ичных строк, не содержащих повторяющихся подстрок длины
${\le 3}$ (т.е. не содержащих подстрок вида
$a a$,
$a b a b$ и
$a b c a b c$), образует код, исправляющий произвольное количество мутаций типа тандемных дупликаций длины
${\le 3}$. Иными словами, любые две такие строки различимы в том смысле, что из них не могут образоваться одинаковые строки под действием некоторого количества тандемных дупликаций длины
${\le 3}$. Показано, что этот код асимптотически оптимален по скорости, т.е. представляет собой максимальное множество различимых строк с точностью до субэкспоненциального множителя. Этот результат дает решение задачи о пропускной способности с нулевой ошибкой для последнего оставшегося случая каналов с тандемными дупликациями, удовлетворяющих свойству “единственности корневых строк”.
Ключевые слова:
тандемная дупликация, повторение тандема, ошибка дупликации, ошибка повторения, вклейка, хранение информации на основе ДНК, исправление ошибок, пропускная способность с нулевой ошибкой, код с ограничением, строка без повторений.
УДК:
621.391 :
519.724.2 Поступила в редакцию: 04.10.2021
После переработки: 20.04.2022
Принята к печати: 21.04.2022
DOI:
10.31857/S0555292322020028
Полный текст:
PDF файл (228 kB)