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

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

Сегмент с максимальным средним значением (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].

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

Пусть задана последовательность чисел 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)