Просмотр кода страницы Сегмент максимальной плотности

== Ключевые слова и синонимы ==
Сегмент с максимальным средним значением (''Maximum-average segment'')

== Постановка задачи ==
Пусть имеются последовательность чисел A = ha1, a2, ..., ani и два положительных целых числа L и U, таких, что выполняется соотношение 1 < L < U < n. Задача нахождения сегмента максимальной плотности заключается в поиске идущей подряд подпоследовательности, т. е. сегмента или подстроки, из последовательности A длиной не менее L и не более U, такой, что среднее значение чисел в подпоследовательности максимально.

== Основные результаты ==
Если нет ограничений по длине, то, очевидно, сегментом с максимальной плотностью является максимальное число в последовательности. Сначала рассмотрим задачу, в которой накладывается только нижнее ограничение по длине L. Заметив, что длина самого короткого сегмента с максимальной плотностью и длиной не менее L составляет не более 2L - 1, Хуан [7] представил алгоритм с временем выполнения O(nL). Лин и др. [ ] предложили новый метод, называемый декомпозицией со смещением вправо, для разбиения каждого суффикса A на сегменты со смещением вправо и строго убывающими средними значениями. Декомпозиция со смещением вправо может быть выполнена за время O(n); она позволяет для каждой позиции i найти идущую подряд подпоследовательность A, начинающуюся с этой позиции, такую, что среднее значение чисел в подпоследовательности максимально. На основе декомпозиции со смещением вправо Лин и др. [ ] разработали алгоритм с временем выполнения O(nlogL) для задачи о сегментах максимальной плотности с нижней границей L, который был усовершенствован до времени O(n) Голдвассером и коллегами [ ]. Kim [ ] предложил другой алгоритм O(n), сведя задачу к задаче вычислительной геометрии о максимальном наклоне. Что касается задачи, учитывающей как L, так и U, Чунг и Лу [4] обошли построение декомпозиции со смещением вправо и предложили алгоритм с временем выполнения O(n).


Следует отметить, что тесно связанная с этой задача в области интеллектуального анализа данных, которая в основном имеет дело с двоичными последовательностями, была независимо сформулирована и изучена Фукудой и др. [5].


'''Расширение на несколько сегментов'''

Пусть задана последовательность чисел A = ha1;a2;:::; ani и два положительных целых числа L и k, где k < j. Обозначим за d(A[i;j]) плотность сегмента A[i;j], определяемую как (ai + ai+1 + ••• + aj)/(j - i + 1). Задача состоит в том, чтобы найти k непересекающихся сегментов fs1;s2 • • • skg из последовательности A, каждый из которых имеет длину не менее L, таких, что Xa<;<it^(si) максимально. Чен и др. [3] предложили алгоритм с временем выполнения O(nkL), а улучшенный алгоритм с временем выполнения O(nL + k2L2) представили Бергквист и Дамашке [ ]. Лю и Чао [11] предложили алгоритм с временем выполнения O(n + k2LlogL).
 
== Применение ==
У всех организмов гуанин-цитозиновый нуклеотидный состав (GC-состав) оснований ДНК составляет от 25 до 75%, причем наибольшие колебания наблюдаются у бактерий. Геномы млекопитающих обычно имеют GC-состав на уровне 45-50%. Некрутенко и Ли [ ] показали, что степень неоднородности состава геномной последовательности сильно коррелирует с ее GC-составом. Гены преимущественно находятся в классах изохор с наибольшим содержанием гуанина-цитозина. Следовательно, поиск регионов с высоким содержанием гуанина-цитозина является важной задачей в распознавании генов и сравнительной геномике.


Имея последовательность ДНК, можно попытаться найти сегменты длиной не менее L с наибольшим соотношением гуанина и цитозина. В частности, каждому из нуклеотидов C (цитозин) и G (гуанин) присваивается балл 1, а каждому из нуклеотидов A (аденин) и T (тимин) – балл 0.
Последовательность ДНК:    ATGACTCGAGCTCGTCA Двоичная последовательность: 00101011011011010


Сегменты с максимальным средним значением двоичной последовательности соответствуют сегментам с самым высоким GC-составом в последовательности ДНК. Более подробную информацию о вариантах применения можно найти в работах [1, 9, 10, 13, 14, 15].

== Открытые вопросы ==
Наилучшая асимптотическая временная сложность алгоритмов для задачи о нескольких сегментах максимальной плотности составляет O(n + k2LlogL). Можно ли решить эту задачу за время O(n)?

== См. также ==
* [[Сегмент с максимальным баллом и ограничениями по длине]]

== Литература ==

1.	Arslan A., Egecioglu, O, Pevzner, P.: A new approach to sequence comparison: normalized sequence alignment. Bioinformatics 17, 327-337 (2001)

2.	Bergkvist, A., Damaschke, P.: Fast algorithms for finding disjoint subsequences with extremal densities. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation. LNCS, vol. 3827, pp. 714-723 (2005)

3.	Chen, Y.H., Lu, H.I., Tang, C.Y.: Disjoint segments with maximum density. In: Proceedings of the 5th Annual International Conference on Computational Science, pp. 845-850 (2005)

4.	Chung, K.-M., Lu, H.-I.: An optimal algorithm for the maximum-density segment problem. SIAM. J. Comput. 34, 373-387 (2004)

5.	Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Mining Optimized Association Rules for Numeric Attributes. J. Comput. Syst. Sci. 58,1-12 (1999)

6.	Goldwasser, M.H., Kao, M.-Y., Lu, H.-I.: Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J. Comput. Syst. Sci. 70, 128-144 (2005)

7.	Huang, X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Comput. Appl. Biosci. 10,219-225 (1994)

8.	Kim, S.K.: Linear-time algorithm for finding a maximum-density segment of a sequence. Inf. Process. Lett. 86, 339-342 (2003)

9.	Lin, Y.-L., Huang, X., Jiang, T., Chao, K.-M.: MAVG: locating non-overlapping maximum average segments in a given sequence. Bioinformatics 19,151-152 (2003)

10.	Lin, Y.-L., Jiang, T., Chao, K.-M.: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. Syst. Sci. 65, 570-586 (2002)

11.	Liu, H.-F., Chao, K.-M.: On locating disjoint segments with maximum sum of densities. In: Proceedings of the 17th Annual International Symposium on Algorithms and Computation. LNCS, vol. 4288, pp. 300-307 (2006)

12.	Nekrutenko, A., Li, W.H.: Assessment of compositional heterogeneity within and between eukaryotic genomes. Genome Res. 10,1986-1995(2000)

13.	Stojanovic, N., Florea, L., Riemer, C., Gumucio, D., Slightom, J., Goodman, M., Miller, W., Hardison, R.: Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions. Nucl. Acid. Res. 19, 3899-3910 (1999)

14.	Stojanovic, N., Dewar, K.: Identifying multiple alignment regions satisfying simple formulas and patterns. Bioinformatics 20,2140-2142(2005)

15.	Zhang, Z., Berman, P., Wiehe, T., Miller, W.: Post-processing long   pairwise  alignments.   Bioinformatics   15,   1012-1019 (1999)