|
Биоинформатика
О количестве перекрытий слов в паттернах
Е. И. Фурлетоваa, М. А. Ройтбергabc a Институт математических проблем биологии, Российская академия наук, Пущино, Московская область, Россия
b Московский физико-технический институт, Долгопрудный,
Московская область, Россия
c НИУ Высшая школа экономики, Москва, Россия
Аннотация:
Изучалась задача оценки количества перекрытий в паттерне — наборе слов в некотором алфавите $A$, имеющих одну и ту же длину $m$. Получены теоретические и экспериментальные оценки количества перекрытий для паттернов двух видов. Первый из них — это случайные паттерны, для которых верна равномерная вероятностная модель: все буквы в алфавите $A$ и, соответственно, все слова длины $m$ равновероятны. Доказано, что среднее количество перекрытий $P$ для случайных паттернов, состоящих из $n$ слов длины $m$, линейно зависит от размера паттерна $n$ и не зависит от длины слов в паттерне. В проведенных компьютерных экспериментах отношение $P/n$ менялось в пределах от $0.33$ до $1.06$; теоретические оценки этого отношения для тех же паттернов не превосходят $1.67$. Вторым видом паттернов, изученных в статье, являются паттерны, заданные матрицами позиционных весов из базы данных HOCOMOCO и пороговыми весами. Для этих паттернов отношение количества перекрытий к количеству слов в экспериментах менялось от $0.004$ до $1$, для более половины паттернов это отношение меньше $0.1$.
Ключевые слова:
перекрытие, паттерн, вхождение паттерна в последовательность.
Материал поступил в редакцию 19.11.2015, опубликован 27.01.2016
Образец цитирования:
Е. И. Фурлетова, М. А. Ройтберг, “О количестве перекрытий слов в паттернах”, Матем. биология и биоинформ., 11:1 (2016), 14–23
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mbb248 https://www.mathnet.ru/rus/mbb/v11/i1/p14
|
Статистика просмотров: |
Страница аннотации: | 156 | PDF полного текста: | 54 | Список литературы: | 35 |
|