Сегмент с максимальным баллом и ограничениями по длине
Ключевые слова и синонимы
Кратчайший путь (Shortest path); самый длинный путь (Longest path)
Постановка задачи
Дана последовательность чисел [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], такой, что сумма чисел в подпоследовательности максимальна.
Основные результаты
Задача нахождения сегмента с максимальной суммой без ограничений по длине может быть решена за линейное время с помощью алгоритма Кадане [2]. Хуан расширил рекуррентное соотношение, примененное в работе [2], для решения задачи о сегменте с максимальной суммой, и вывел линейный по времени алгоритм для вычисления сегмента с максимальной суммой длиной не менее L. Лин и др. [10] предложили алгоритм с временем выполнения O(n) для задачи о сегменте с максимальной суммой и ограничениями L и U, а его онлайн-версия была представлена Фаном и коллегами в [8].
Расширение на несколько сегментов
Вычисление k наибольших сумм по всем возможным сегментам является естественным расширением задачи о сегментах с максимальной суммой. Это расширение рассматривалось с двух точек зрения, одна из которых допускает перекрытие сегментов, а вторая – нет.
Линейные по времени алгоритмы для нахождения всех непересекающихся максимальных сегментов были предложены в [3, 12]. С другой стороны, можно сосредоточиться на поиске k сегментов с максимальной суммой, пересечение которых допускается. Наивный подход заключается в выборе k наибольших из сумм всех возможных смежных подпоследовательностей, что требует времени O(n2). Бэй и Такаока [ ] представили алгоритм с временем выполнения O(kn) для задачи о нахождении k максимальных сегментов. Лю и Чао [11] отметили, что задача о нахождении k сегментов с максимальной суммой может быть решена за время O(n + k) [ ], и предложили алгоритм с временем выполнения O(n + k) для поска k с максимальной суммой в условиях ограничения длины.
Применение
Алгоритмы для задачи о сегментах с максимальной суммой находят применение в поиске богатых гуанином-цитозином областей в геномной ДНК, постобработке выравнивания последовательностей и аннотировании выравнивания нескольких последовательностей. Более подробную информацию можно найти в работах [3, 4, 5, 6, 10, 12, 13, 14, 15].
Открытые вопросы
Было бы любопытно рассмотреть случаи более высоких размерностей.
См. также
Литература
1. Bae, S.E., Takaoka, T.: Algorithms for the problem of k maximum sums and a VLSI algorithm for the k maximum subarrays problem. Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 247-253 (2004)
2. Bentley, J.: Programming Pearls. Addison-Wesley, Reading (1986)
3. Chen, K.-Y., Chao, K.-M.: On the range maximum-sum segment query problem. Proceedings of the 15th International Symposium on Algorithms And Computation. LNCS 3341, 294-305 (2004)
4. Chen, K.-Y., Chao, K.-M.: Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint. Inf. Process. Lett. 96,197-201 (2005)
5. Cheng, C.-H., Chen, K.-Y., Tien, W.-C., Chao, K.-M.: Improved algorithms for the k maximum-sum problems. Proceedings of the 16th International Symposium on Algorithms And Computation. Theoret. Comput. Sci. 362:162-170 (2006)
6. Csuros, M.: Maximum-scoring segment sets. IEEE/ACM Trans. Comput. Biol. Bioinform. 1,139-150 (2004)
7. Eppstein, D.: Finding the k Shortest Paths. SIAM J. Comput. 28, 652-673(1998)
8. Fan, T.-H., Lee, S., Lu, H.-I., Tsou, T.-S., Wang, T.-C., Yao, A.: An optimal algorithm for maximum-sum segment and its application in bioinformatics. Proceedings of the Eighth International Conference on Implementation and Application of Automata. LNCS 2759, 251-257 (2003)
9. Huang, X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Comput. Appl. Biosci. 10, 219-225(1994)
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.: Algorithms for Finding the Weight-Constrained k Longest Paths in a Tree and the Length-Constrained k Maximum-Sum Segments of a Sequence. The oret. Comput. Sci. in revision (2008)
12. Ruzzo, W.L., Tompa, M.: A linear time algorithm for finding all maximal scoring subsequences. Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology, pp. 234-241 (1999)
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. Nucleic Acids 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)