Сегмент максимальной плотности

Ключевые слова и синонимы

Сегмент с максимальным средним значением (Maximum-average segment)

Постановка задачи

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

Основные результаты

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

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

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

Пусть задана последовательность чисел [math]\displaystyle{ A = \langle a_1, a_2, ..., a_n \rangle }[/math] и два положительных целых числа [math]\displaystyle{ L }[/math] и [math]\displaystyle{ k }[/math], где [math]\displaystyle{ k \le \frac{n}{L} }[/math]. Обозначим за [math]\displaystyle{ d(A[i, j]) }[/math] плотность сегмента [math]\displaystyle{ A[i, j] }[/math], определяемую как [math]\displaystyle{ (a_i + a_{i + 1} + \dots + a_j)/(j - i + 1) }[/math]. Задача состоит в том, чтобы найти [math]\displaystyle{ k }[/math] непересекающихся сегментов [math]\displaystyle{ \{s_1, s_2, ..., s_k\} }[/math] из последовательности [math]\displaystyle{ A }[/math], каждый из которых имеет длину не менее [math]\displaystyle{ L }[/math], таких, что сумма [math]\displaystyle{ \sum_{1 \le i \le k} d(s_i) }[/math]максимальна. Чен и др. [3] предложили алгоритм с временем выполнения [math]\displaystyle{ O(nkL) }[/math], а улучшенный алгоритм с временем выполнения [math]\displaystyle{ O(nL + k^2L^2) }[/math] представили Бергквист и Дамашке [2]. Лю и Чао [11] предложили алгоритм с временем выполнения [math]\displaystyle{ O(n + k^2 \; L \; log \; L) }[/math].

Применение

У всех организмов гуанин-цитозиновый нуклеотидный состав (GC-состав) оснований ДНК составляет от 25 до 75%, причем наибольшие колебания наблюдаются у бактерий. Геномы млекопитающих обычно имеют GC-состав на уровне 45-50%. Некрутенко и Ли [12] показали, что степень неоднородности состава геномной последовательности сильно коррелирует с ее GC-составом. Гены преимущественно находятся в классах изохор с наибольшим содержанием гуанина-цитозина. Следовательно, поиск регионов с высоким содержанием гуанина-цитозина является важной задачей в распознавании генов и сравнительной геномике.

Имея последовательность ДНК, можно попытаться найти сегменты длиной не менее [math]\displaystyle{ L }[/math] с наибольшим процентом гуанина и цитозина. В частности, каждому из нуклеотидов [math]\displaystyle{ C }[/math] (цитозин) и [math]\displaystyle{ G }[/math] (гуанин) присваивается балл 1, а каждому из нуклеотидов [math]\displaystyle{ A }[/math] (аденин) и [math]\displaystyle{ T }[/math] (тимин) – балл 0.

  Последовательность ДНК:   [math]\displaystyle{ \; \;  }[/math]  ATGACTCGAGCTCGTCA 
  Двоичная последовательность: 00101011011011010

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

Открытые вопросы

Наилучшая асимптотическая временная сложность алгоритмов для задачи о нескольких сегментах максимальной плотности составляет [math]\displaystyle{ O(n + k^2 \; L \; log \; L) }[/math]. Можно ли решить эту задачу за время [math]\displaystyle{ O(n) }[/math]?

См. также

• Сегмент с максимальным баллом и ограничениями по длине

Литература

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)