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

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

== Постановка задачи ==
Пусть имеются последовательность чисел <math>A = \langle a_1, a_2, ..., a_n \rangle</math> и два положительных целых числа <math>L</math> и <math>U</math>, таких, что выполняется соотношение <math>1 \le L \le U \le n</math>. Задача нахождения сегмента с максимальной суммой заключается в поиске идущей подряд подпоследовательности, т. е. сегмента или подстроки, из последовательности <math>A</math> длиной не менее <math>L</math> и не более <math>U</math>, такой, что среднее значение чисел в подпоследовательности максимально.

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


Следует отметить, что тесно связанная с этой задача в области интеллектуального анализа данных, которая в основном имеет дело с двоичными последовательностями, была независимо сформулирована и изучена Фукудой и др. [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)