Сегмент максимальной плотности: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сегмент с максимальным средним значением (''Maximum-average segment'') == Постановка задачи == Пусть имеются последовательность чисел A = ha1, a2, ..., ani и два положительных целых числа L и U, таких, что выполняется соотношение 1 < L < U < n. Задача на...») |
Irina (обсуждение | вклад) м (→Применение) |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеются последовательность чисел A = | Пусть имеются последовательность чисел <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>, такой, что среднее значение чисел в подпоследовательности максимально. | ||
== Основные результаты == | == Основные результаты == | ||
Если нет ограничений по длине, то, очевидно, сегментом с максимальной плотностью является максимальное число в последовательности. Сначала рассмотрим задачу, в которой накладывается только нижнее ограничение по длине L. Заметив, что длина самого короткого сегмента с максимальной плотностью и длиной не менее L составляет не более 2L - 1, Хуан [7] представил алгоритм с временем выполнения O(nL). Лин и др. [ ] предложили новый метод, называемый декомпозицией со смещением вправо, для разбиения каждого суффикса A на сегменты со смещением вправо и строго убывающими средними значениями. Декомпозиция со смещением вправо может быть выполнена за время O(n); она позволяет для каждой позиции i найти идущую подряд подпоследовательность A, начинающуюся с этой позиции, такую, что среднее значение чисел в подпоследовательности максимально. На основе декомпозиции со смещением вправо Лин и др. [ ] разработали алгоритм с временем выполнения O( | Если нет ограничений по длине, то, очевидно, сегментом с максимальной плотностью является максимальное число в последовательности. Сначала рассмотрим задачу, в которой накладывается только нижнее ограничение по длине <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>. | ||
| Строка 14: | Строка 14: | ||
'''Расширение на несколько сегментов''' | '''Расширение на несколько сегментов''' | ||
Пусть задана последовательность чисел A = | Пусть задана последовательность чисел <math>A = \langle a_1, a_2, ..., a_n \rangle</math> и два положительных целых числа <math>L</math> и <math>k</math>, где <math>k \le \frac{n}{L}</math>. Обозначим за <math>d(A[i, j])</math> ''плотность'' сегмента <math>A[i, j]</math>, определяемую как <math>(a_i + a_{i + 1} + \dots + a_j)/(j - i + 1)</math>. Задача состоит в том, чтобы найти <math>k</math> непересекающихся сегментов <math>\{s_1, s_2, ..., s_k\}</math> из последовательности <math>A</math>, каждый из которых имеет длину не менее <math>L</math>, таких, что сумма <math>\sum_{1 \le i \le k} d(s_i)</math>максимальна. Чен и др. [3] предложили алгоритм с временем выполнения <math>O(nkL)</math>, а улучшенный алгоритм с временем выполнения <math>O(nL + k^2L^2)</math> представили Бергквист и Дамашке [2]. Лю и Чао [11] предложили алгоритм с временем выполнения <math>O(n + k^2 \; L \; log \; L)</math>. | ||
== Применение == | == Применение == | ||
У всех организмов гуанин-цитозиновый нуклеотидный состав (GC-состав) оснований ДНК составляет от 25 до 75%, причем наибольшие колебания наблюдаются у бактерий. Геномы млекопитающих обычно имеют GC-состав на уровне 45-50%. Некрутенко и Ли [ ] показали, что степень неоднородности состава геномной последовательности сильно коррелирует с ее GC-составом. Гены преимущественно находятся в классах изохор с наибольшим содержанием гуанина-цитозина. Следовательно, поиск регионов с высоким содержанием гуанина-цитозина является важной задачей в распознавании генов и сравнительной геномике. | У всех организмов гуанин-цитозиновый нуклеотидный состав (GC-состав) оснований ДНК составляет от 25 до 75%, причем наибольшие колебания наблюдаются у бактерий. Геномы млекопитающих обычно имеют GC-состав на уровне 45-50%. Некрутенко и Ли [12] показали, что степень неоднородности состава геномной последовательности сильно коррелирует с ее GC-составом. Гены преимущественно находятся в классах изохор с наибольшим содержанием гуанина-цитозина. Следовательно, поиск регионов с высоким содержанием гуанина-цитозина является важной задачей в распознавании генов и сравнительной геномике. | ||
Имея последовательность ДНК, можно попытаться найти сегменты длиной не менее <math>L</math> с наибольшим процентом гуанина и цитозина. В этом случае каждому из нуклеотидов <math>C</math> (цитозин) и <math>G</math> (гуанин) присваивается балл 1, а каждому из нуклеотидов <math>A</math> (аденин) и <math>T</math> (тимин) – балл 0. | |||
Последовательность ДНК: <math>\; \; </math> ATGACTCGAGCTCGTCA | |||
Последовательность ДНК: | Двоичная последовательность: 00101011011011010 | ||
Сегменты с максимальным средним значением | Сегменты двоичной последовательности с максимальным средним значением соответствуют сегментам с самым высоким GC-составом в последовательности ДНК. Более подробную информацию о вариантах применения можно найти в работах [1, 9, 10, 13, 14, 15]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Наилучшая асимптотическая временная сложность алгоритмов для задачи о нескольких сегментах максимальной плотности составляет O(n + | Наилучшая асимптотическая временная сложность алгоритмов для задачи о нескольких сегментах максимальной плотности составляет <math>O(n + k^2 \; L \; log \; L)</math>. Можно ли решить эту задачу за время <math>O(n)</math>? | ||
== См. также == | == См. также == | ||
Текущая версия от 10:55, 11 января 2026
Ключевые слова и синонимы
Сегмент с максимальным средним значением (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)