Personal tools

Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications

— filed under:

Dr.Michael H. Goldwasser, Loyola State University

  • Computer Science Seminar
When Mon, Feb 03, 2003
from 04:10 PM to 05:00 PM
Where RH 320
Add event to calendar vCal

Abstract: We study an abstract optimization problem arising from biomolecular sequence analysis. One motivation is the desire to identify GC-rich segments of DNA sequences. For a sequence A = {a1, a2, ..., an} of real numbers, a segment A(i,j) is a consecutive subsequence of A starting with index i and ending with index j. The maximum-density segment problem takes A and two values 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. We provide a relatively simple, O(n)-time algorithm for this problem. This improves upon the O(n log L)-time algorithm by Lin, Jiang and Chao, for the case where U is unbounded, and upon a trivial O(n(U-L+1))-time algorithm when both L and U are specified. This is joint work with Ming-Yang Kao and Hsueh-I Lu.

« February 2018 »