Анализ ДНК--последовательностей при помощи аппарата Марковских цепей

Усоцкая Н.С.

Новосибирский государственный университет

usotskaya@gmail.com

Аннотация

Статистическая структура последовательности ДНК представляет значительный интерес для молекулярной биологии, генетики и теории эволюции (см. [1] ─ [5]). Один из подходов к исследованию последовательностей ДНК состоит в их описании Марковскими процессами с различной памятью и последующим статистическим оцениванием параметров ([2], [5]). В данной работе проводятся оценки "памяти" (или связности) генетических текстов, используя недавно предложенный в [6] алгоритм для проверки гипотез.

Введение

Проблема исследования статистической структуры ДНК стала особенно актуальной после накопления больших объемов данных при секвенцировании геномов различных организмов. Был разработан ряд подходов к статистическому анализу генетических текстов. В настоящее время в разностороннем исследовании структуры ДНК заинтересованы молекулярная биология, генетика, теория эволюции, фармакология и другие отрасли. Данная тематика привлекает внимание многих исследователей во всем мире, ей посвящены ряд работ (например, [1] ─ [5]), кроме того, издаются специализированные журналы, такие как Bioinformatics (http://bioinformatics.oxfordjournals.org/). Одним из самых популярных являлось описание последовательностей ДНК при помощи Марковских процессов различной памяти (см. [1], [2]).

Мы развили данный подход, используя предложенный в [3] тест, позволяющий оценить "память" источника, породившего некоторую последовательность над конечным алфавитом. Оценки "памяти" представляют интерес, так как позволяют определить глубину взаимозависимости между символами в последовательности. В [4] упомянут ряд предположений о возможной глубине зависимости между символами в последовательностях ДНК, которые варьировались от 3-6 оснований до 1-10000 оснований. То есть вопрос о глубине зависимости для последовательностей ДНК не был решен однозначно. Возможно, поэтому до сих пор попытки моделировать генетические тексты основывались на Марковских моделях порядка не выше 2 ([1], [2]).

В результате проведенных экспериментов выяснилось, что "память" рассмотренных организмов в основном превосходит значение 2, поэтому для корректного моделирования последовательностей ДНК необходимо выбирать Марковские процессы более высокого порядка, которые позволяют "уловить" более тонкие закономерности в генетических текстах различных организмов.

1. Оценка "памяти" источника

Данный раздел посвящен краткому описанию предложенного в [Ryabko] теста сериальной независимости для проверки гипотез, который в дальнейшем будет использоваться для оценки "памяти" генетических текстов различных живых организмов.

Данный тест анализирует последовательности символов над конечным алфавитом, причем предполагается, что последовательности были порождены Марковским процессом конечной памяти с дискретным временем. Другими словами, предполагается, что для Марковского источника порядка m вероятность порождения следующего символа (a) зависит только от m предыдущих элементов последовательности, то есть:

Тест из [6] использует некоторый универсальный код (или метод сжатия данных), который необходимо выбрать до начала экспериментов. В качестве такого универсального кода может служить один из стандартных методов сжатия данных (так называемые архиваторы).

Приведем формальное описание теста сериальной независимости.

Пусть образец X для анализа представлен r последовательностями порожденными неизвестным источником, и пусть

Пусть φ - некоторый однозначно декодируемый код, то есть метод сжатия данных без потери информации (в качестве такого универсального кода может быть рассмотрен любой стандартный архиватор). Кроме того, обозначает эмпирическую энтропию Шеннона порядка m:

где а обозначает количество вхождений подслова v в слово xⁱ.

Проверяется основная гипотеза , утверждающая, что источник, породивший данный образец X, является Марковский, причем порядок источника не превышает m, (m ≥0). Альтернативная гипотеза утверждает, что образец X порожден стационарным и эргодическим источником, чей порядок больше m.

Используя приведенные обозначения, тест формулируется следующим образом:

гипотеза принимается, если:

где α из (0, 1) ─ требуемый уровень значимости. В противном случае принимается гипотеза .

В [6] было доказано, что для любого кода φ ошибка первого рода

не превосходит α, а для универсального кода φ ошибка второго рода стремится к нулю при t, стремящемся к бесконечности.

Приведенный тест на сериальную независимость будет использоваться в следующем разделе для оценивания "памяти" генетических текстов различных организмов.

2. Экспериментальное исследование генетических текстов

В данном разделе будут представлены результаты экспериментов, проведенных для анализа последовательностей ДНК ряда живых организмов. В качестве инструмента анализа использовался статистический тест из [6], рассмотренный в предыдущем разделе.

2.1 Основные понятия генетики

Прежде чем перейти к рассмотрению проблем молекулярной биологии, связанных с анализом последовательностей ДНК, рассмотрим основные биологические понятия, которые будут использоваться в дальнейшем.

Как известно, ДНК любого организма содержит генетическую информацию о нем. Молекула ДНК представляет собой длинную двойную спираль нуклеотидов, каждый из которых состоит из дезоксирибозы, фосфатной группы и одного из четырех азотистых оснований ─ аденин (A), цитозин (C), гуанин (G) и тимин (T). Таким образом, последовательность ДНК можно рассматривать как порожденную некоторым источником с четырехбуквенным алфавитом ─ {A, C, G, T} (см., например, [8]

Далее последовательности ДНК "разбиваются" на триплеты ─ тройки символов, которые носят название кодоны (см., например, [8]). Кодон ─ это единица генетического кода, тройка нуклеотидных оснований в ДНК или РНК, кодирующих включение одной аминокислоты. В свою очередь последовательности кодонов формируют гены.

Гены ─ это участки ДНК, несущие какую-либо целостную информацию ─ о строении одной молекулы белка или одной молекулы РНК. Последовательность кодонов в гене определяет последовательность аминокислот в цепи белка, кодируемого данным геном.

2.2 Экспериментальное исследование "памяти" генетических текстов

В [3] упомянут ряд работ, в которых высказывались предположения о том, насколько длинными могут быть зависимости между символами в последовательностях ДНК. Предположения о порядке зависимости сильно варьировался по количеству оснований. Возможно, именно поэтому для моделирования последовательностей ДНК до сих пор обычно используются Марковские процессы низкого порядка ─ нулевого, первого или второго (см., например, [2], [5]). С целью оценить "память" генетических текстов нами был проведен ряд экспериментов с использованием статистического теста для проверки гипотез, рассмотренного в разделе 1.

Проведенный анализ позволил впервые получить ряд данных, ранее не известных. В частности, оказалось, что значение "памяти" сильно варьируется даже у биологически близких организмов, и лежит в пределах от 2 до 9 для рассмотренных генетических текстов.

Для исследования "памяти" генетических текстов различных видов был рассмотрен ряд прокариотов. Прокариоты ─ это надцарство одноклеточных живых организмов, не обладающих оформленным клеточным ядром. К прокариотам относят царства

бактерий и архебактерий.

Среди них рассматривались геномы 38 архебактерий и 43 бактерии (в том числе рассматривались все хромосомы, если таковые имелись). Все рассмотренные последовательности ДНК были взяты из базы данных [9].

Результаты расчетов для архебактерий представлены в таблице 1, а для бактерий ─ в таблице 2.

Таблицы 1 ─ 2 составлены единообразно. В колонке "Название" приведено латинское наименование организма. Графа "Chr" указывает на номер рассматриваемой хромосомы, если таковая имеется. Колонка "Длина" содержит количество нуклеотидов в цепочке ДНК. В колонке "Количество генов" содержится количество различных генов в рассматриваемой последовательности ДНК (данные взяты из [9]). В колонке "Память" находятся результаты оценки "памяти" генетических текстов представленных организмов на основе тестов из [6].

Предварительный анализ позволил предположить, что длина генетических текстов и количество генов статистически связаны с "памятью" последовательностей ДНК, определенной тестом на сериальную независимость. Для проверки этой гипотезы были посчитаны коэффициенты корреляции между парами выборок данных:

· между "памятью" и длиной последовательности ДНК,

· между "памятью" и количеством генов.

В результате получены следующие коэффициенты корреляции:

Вид организмов	"Память" и длина	"Память" и количество генов
Архебактерии	0.63	0.53
Бактерии	0.37	0.35

Таким образом, мы видим, что характеристика "памяти" генетических текстов представляет собой самостоятельный биологический интерес, поскольку корреляция ее со стандартными параметрами последовательностей ДНК существует, но модуль ее не близок к нулю или единице. Следовательно, характеристика "памяти" генетических текстов может предоставить новую информацию о структуре ДНК.

Отметим и тот неожиданный факт, что "память" последовательности ДНК, даже для биологически близких огранизмов (принадлежащих одному роду) может существенно отличаться. В качестве примера приведем архебактерии рода Sulfolobus и бактерии рода Bordetella. Археобактерий Sulfolobus acidocaldarius DSM 639, Sulfolobus solfataricus P2 и Sulfolobus tokodaii str. 7 имеют сопоставимую длину генома ─ от 2.1 до 2.8 Мб, однако определенная тестом "память" существенно отличается ─ 3, 9 и 7 соответственно. Что касается бактерий Bordetella bronchiseptica, Bordetella parapertussis и Bordetella pertussis, то размер генома в данном случае варьируется от 4 до 5.3 Мб, а определенная тестом "память" имеет значения 3, 4 и 8 соответственно, причем самая большая память (8) определена для самого короткого генома ─ Bordetella pertussis. Таким образом, приведенные примеры показывают, что "глубина взаимозависимости" между символами в последовательностях ДНК может существенно варьироваться для близких видов.

Можно сделать вывод, что данный метод определения "памяти" генетического текста может помочь при выборе корректной модели при моделировании последовательностей ДНК, поскольку, согласно результатам теста сериальной независимости, "память" генетических текстов обычно больше, чем 2. Тогда как обычно при моделировании генетических текстов используют Марковские модели низкого порядка.

Список литературы

[1] Chen X., Kwong S., Li M. A Compression Algorithm for DNA Sequences and Its Applications in Genome Comparison // In Proceedings of the 10th Workshop on Genome Informatics (GIW-99), 1999. P. 51─61.

[2] Farach M., Noordewier M., Savari S., Shepp L., Wyner A., Ziv A. On the entropy of DNA: Algorithms and measurements based on memory and rapid convergence // Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994. P. 48─57.

[3] Li W. The Study of Correlation Structures of DNA Sequences: A Critical Review // Computers and Chemistry, 1997. Vol. 21, № 4. P. 257─271.

[4] Oprea I., Pasca S., Gavrila V. Method of DNA Analysis Using the Estimation of the Algorithmic Complexity // Leonardo Electronic Journal of Practices and Technologies, 2004. Vol. 3, № 5. P. 53─66.

[5] Simons G., Yao Y-Ch., Morton G. Global Markov models for eukaryote nucleotide data // Journal of Statistical Planning and Inference, 2005. Vol. 130. P. 251─275.

[6] Ryabko B., Astola J. Universal codes as a basis for time series testing // Statistical Methodology, 2006. Vol. 3. P. 375─397.

[7] Karp R.M. Mathematical Challenges from Genomics and Molecular Biology // Notices of the AMS, 2002. Vol. 49, № 5. P. 544─553.

[8] Боринская С.А., Гельфанд М.С., Миронов А.А. Компьютерная геномика ─ новая эра // Российская наука на заре нового века: Сб. науч.-поп. ст., М.: Научный мир, 2001. С. 249─255.

[9] National Center for Biotechnology Information: www.ncbi.nlm.nih.gov.

Таблица 1. Результаты оценивания "памяти" для архебактерий

№	Название	Chr	Длина	Кол-во генов	Память
1	Aeropyrum pernix K1		1669696	1752	3
2	Archaeoglobus fulgidus		2178400	2486	3
3	Haloarcula marismortui ATCC 43049	I	3131724	3186	3
4		II	288050	285	4
5	Halobacterium sp. NRC-1		2014239	2127	3
6	Haloquadratum walsbyi DSM 16790		3132494	2875	7
7	Hyperthermus butylicus DSM 5456		1667163	1672	3
8	Metallosphaera sedula DSM 5348		2191517	2341	3
9	Methanocaldococcus jannaschii DSM 2661		1664970	1772	3
10	Methanococcoides burtonii DSM 6242		2575032	2497	8
11	Methanococcus maripaludis C5		1780761	1880	6
12	Methanococcus maripaludis S2		1661137	1772	5
13	Methanocorpusculum labreanum Z		1804962	1819	6
14	Methanoculleus marisnigri JR1		2478101	2555	4
15	Methanopyrus kandleri AV19		1694969	1729	3
16	Methanosaeta thermophila PT		1879471	1781	7
17	Methanosarcina barkeri str. Fusaro		4837408	3811	9
18	Methanosarcina mazei Go1		4096345	3436	8
19	Methanosarcina acetivorans C2A		5751492	4721	9
20	Methanosphaera stadtmanae DSM 3091		1767403	1588	7
21	Methanospirillum hungatei JF-1		3544738	3304	8
22	Nanoarchaeum equitans Kin4-M		490885	582	3
23	Natronomonas pharaonis DSM 2160		2595221	2726	3
24	Picrophilus torridus DSM 9790		1545895	1581	3
25	Pyrobaculum aerophilum str. IM2		2222430	2706	3
26	Pyrobaculum arsenaticum DSM 13514		2121076	2407	3
27	Pyrobaculum calidifontis JCM 11548		2009313	2200	3
28	Pyrobaculum islandicum DSM 4184		1826402	2062	5
29	Pyrococcus abyssi		1765118	1993	3
30	Pyrococcus furiosus DSM 3638		1908256	2228	6
31	Pyrococcus horikoshii OT3		1738505	2005	3
32	Staphylothermus marinus F1		1570485	1646	3
33	Sulfolobus acidocaldarius DSM 639		2225959	2329	3
34	Sulfolobus solfataricus P2		2992245	3031	9
35	Sulfolobus tokodaii str. 7		2694756	2874	7
36	Thermococcus kodakarensis KOD1		2088737	2358	3
37	Thermofilum pendens Hrk 5		1781889	1879	3
38	Thermoplasma acidophilum DSM 1728		1564906	1530	3
39	Thermoplasma volcanium GSS1		1584804	1548	6

Таблица 2. Результаты оценивания "памяти" для бактерий

№	Название	Chr	Длина	Кол-во генов	Память
1	Acidobacteria bacterium Ellin345		5650368	4834	4
2	Acidothermus cellulolyticus 11B		2443540	2217	3
3	Anaplasma marginale St Maries		1197687	1005	8
4	Anaplasma phagocytophilum HZ		1471282	1411	8
5	Aquifex aeolicus		1551335	1580	3
6	Bacillus anthracis Ames		5227293	5630	7
7	Bacillus anthracis str Sterne		5228663	5415	7
8	Bacillus cereus ATCC 10987		5224283	5772	8
9	Bacillus cereus ATCC 14579		5411809	5476	8
10	Bacillus cereus ZK		5300915	5269	8
11	Bacillus clausii KSM-K16		4303871	4204	7
12	Bacillus halodurans		4202352	4171	9
13	Bacillus licheniformis ATCC 14580		4222334	4290	7
14	Bacillus thuringiensis Al Hakam		5257091	4883	8
15	Bacillus thuringiensis konkukian		5237682	5261	8
16	Bacteroides fragilis NCTC 9434		5205140	4347	7
17	Bacteroides fragilis YCH46		5277274	4670	7
18	Bacteroides thetaiotaomicron VPI-5482		6260361	4864	8
19	Bartonella bacilliformis KC583		1445021	1375	8
20	Bartonella henselae Houston-1		1931047	1665	8
21	Bartonella quintana Toulouse		1581384	1356	8
22	Baumannia cicadellinicola Homalodisca coagulata		686194	651	2
23	Bdellovibrio bacteriovorus		3782950	3623	3
24	Bifidobacterium adolescentis ATCC 15703		2089645	1700	6
25	Bifidobacterium longum		2256640	1798	6
26	Bordetella bronchiseptica		5339179	5072	3
27	Bordetella parapertussis		4773551	4467	4
28	Bordetella pertussis		4086189	3867	8
29	Borrelia afzelii PKo		905394	894	6
30	Borrelia burgdorferi		910724	875	6
31	Borrelia garinii PBi		904246	869	6
32	Bradyrhizobium ORS278		7456587	6818	4
33	Brucella abortus 9-941	I	2124241	2200	4
34		II	1162204	1156	3
35	Brucella melitensis	I	2117144	2107	4
36		II	1177787	1157	3
37	Brucella melitensis biovar Abortus	I	2121359	2236	4
38		II	1156948	1182	3
39	Brucella suis 1330	I	2107794	2231	4
40		II	1207381	1220	3
41	Buchnera aphidicola Cc Cinara cedri		416380	397	3
42	Buchnera aphidicola Sg		641454	619	2
43	Buchnera aphidicola str. Bp		615980	550	3
44	Buchnera sp		640681	607	2
45	Burkholderia mallei NCTC 10229	I	2284095	2215	7
46		II	3458208	3409	7
47	Burkholderia mallei NCTC 10247	I	2352693	2412	7
48		II	3495678	3553	8
49	Burkholderia mallei SAVP1	I	1734922	1763	7
50		II	3497479	3532	7
52	Helicobacter pylori 26695		1667867	1630	6
53	Helicobacter pylori J99		1643831	1535	4
54	Staphylococcus aureus RF122		2742531	2665	8
55	Staphylococcus epidermidis ATCC 12228		2499279	2495	8
56	Staphylococcus haemolyticus JCSC1435		2685031	2753	8
57	Streptococcus agalactiae A909		2127858	2136	8
58	Streptococcus pyogenes M1 GAS SF370		1852455	1805	7
59	Streptococcus pyogenes MGAS315		1900535	1951	8
60	Streptococcus thermophilus LMG 18311		1796846	1974	8