Maximum subarray problem: Difference between revisions

Revision as of 22:06, 28 June 2024

Revision as of 22:13, 28 June 2024

Line 29:

== Applications ==

{{expert needed|Computational biology|section|reason=fix inline tags|date=September 2019}}

Maximum subarray problems arise in many fields, such as genomic [[sequence analysis]] and [[computer vision]].

Genomic sequence analysis employs maximum subarray algorithms to identify important biological segments of protein sequences.{{citation needed|date=Marchthat 2020}}have unusual properties, by assigning scores to points within the sequence that are positive when a motif to be recognized is present, and negative when it is not, and then seeking the maximum subarray among these scores. These problems include conserved segments, GC-rich regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge.<ref>{{citation neededharvtxt|date=OctoberRuzzo|Tompa|1999}}; 2017{{harvtxt|Alves|Cáceres|Song|2004}}</ref>

In [[computer vision]], bitmap images generally consist only of positive values, for which the maximum subarray problem is trivial: the result is always the whole array. However, after subtracting a threshold value (such as the average pixel value) from each pixel, so that above-average pixels will be positive and below-average pixels will be negative, the maximum subarray problem can be applied to the modified image to detect bright areas within it.<ref>{{harvtxt|Bae|Takaoka|2006}}; {{harvtxt|Weddell|Read|Thaher|Takaoka|2013}}</ref>

Line 119 ⟶ 118:

==References==

{{Reflist}}

*{{citation

| last1 = Alves | first1 = Carlos E. R.

| last2 = Cáceres | first2 = Edson

| last3 = Song | first3 = Siang W.

| editor1-last = Kranzlmüller | editor1-first = Dieter

| editor2-last = Kacsuk | editor2-first = Péter

| editor3-last = Dongarra | editor3-first = Jack J.

| contribution = BSP/CGM Algorithms for Maximum Subsequence and Maximum Subarray

| doi = 10.1007/978-3-540-30218-6_24

| pages = 139–146

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM/MPI Users' Group Meeting, Budapest, Hungary, September 19-22, 2004, Proceedings

| volume = 3241

| year = 2004}}

*{{citation

| last1 = Backurs

Line 233 ⟶ 246:

| hdl=1813/6370

}}

*{{citation

| last1 = Ruzzo | first1 = Walter L.

| last2 = Tompa | first2 = Martin

| editor1-last = Lengauer | editor1-first = Thomas

| editor2-last = Schneider | editor2-first = Reinhard

| editor3-last = Bork | editor3-first = Peer

| editor4-last = Brutlag | editor4-first = Douglas L.

| editor5-last = Glasgow | editor5-first = Janice I.

| editor6-last = Mewes | editor6-first = Hans-Werner

| editor7-last = Zimmer | editor7-first = Ralf

| contribution = A Linear Time Algorithm for Finding All Maximal Scoring Subsequences

| contribution-url = https://www.aaai.org/Library/ISMB/1999/ismb99-027.php

| pages = 234–241

| publisher = AAAI

| title = Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, August 6–10, 1999, Heidelberg, Germany

| year = 1999}}

*{{citation

| first = Tadao | last = Takaoka