### Abstract

We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A = (equation found) of real numbers, a segment S is a consecutive subsequence (equation found). The width of S is j − i + 1, while the density is (equation found). The maximum-density segment problem takes A and two integers L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. If U = n (or equivalently, U = 2L − 1), we can solve the problem in O(n) time, improving upon the O(n log L)-time algorithm by Lin, Jiang and Chao for a general sequence A. Furthermore, if U and L are arbitrary, we solve the problem in O(n + n log(U − L + 1)) time. There has been no nontrivial result for this case previously. Both results also hold for a weighted variant of the maximum-density segment problem.

Original language | English (US) |
---|---|

Title of host publication | Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings |

Editors | Roderic Guigo, Dan Gusfield |

Publisher | Springer Verlag |

Pages | 157-171 |

Number of pages | 15 |

ISBN (Print) | 3540442111, 9783540442110 |

State | Published - Jan 1 2002 |

Event | 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 - Rome, Italy Duration: Sep 17 2002 → Sep 21 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2452 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 |
---|---|

Country | Italy |

City | Rome |

Period | 9/17/02 → 9/21/02 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings*(pp. 157-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452). Springer Verlag.

}

*Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2452, Springer Verlag, pp. 157-171, 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002, Rome, Italy, 9/17/02.

**Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics.** / Goldwasser, Michael H.; Kao, Ming-Yang; Lu, Hsueh I.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics

AU - Goldwasser, Michael H.

AU - Kao, Ming-Yang

AU - Lu, Hsueh I.

PY - 2002/1/1

Y1 - 2002/1/1

N2 - We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A = (equation found) of real numbers, a segment S is a consecutive subsequence (equation found). The width of S is j − i + 1, while the density is (equation found). The maximum-density segment problem takes A and two integers L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. If U = n (or equivalently, U = 2L − 1), we can solve the problem in O(n) time, improving upon the O(n log L)-time algorithm by Lin, Jiang and Chao for a general sequence A. Furthermore, if U and L are arbitrary, we solve the problem in O(n + n log(U − L + 1)) time. There has been no nontrivial result for this case previously. Both results also hold for a weighted variant of the maximum-density segment problem.

AB - We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A = (equation found) of real numbers, a segment S is a consecutive subsequence (equation found). The width of S is j − i + 1, while the density is (equation found). The maximum-density segment problem takes A and two integers L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. If U = n (or equivalently, U = 2L − 1), we can solve the problem in O(n) time, improving upon the O(n log L)-time algorithm by Lin, Jiang and Chao for a general sequence A. Furthermore, if U and L are arbitrary, we solve the problem in O(n + n log(U − L + 1)) time. There has been no nontrivial result for this case previously. Both results also hold for a weighted variant of the maximum-density segment problem.

UR - http://www.scopus.com/inward/record.url?scp=84957034248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957034248&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84957034248

SN - 3540442111

SN - 9783540442110

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 171

BT - Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings

A2 - Guigo, Roderic

A2 - Gusfield, Dan

PB - Springer Verlag

ER -