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.

« April 2018 »
Upcoming Events
Geometry/ Topology Seminar
Tue, Apr 24, 2018
Necessary and Sufficient Conditions for a Triangle Comparison Theorem, I James Hebda, SLU
Math/CS Club
Wed, Apr 25, 2018
The Mathematical Match Game Brody Johnson, SLU
PhD Oral Defense
Thu, Apr 26, 2018
Finite, fiber-preserving group actions on orientable Seifert manifolds Benjamin Peet, SLU
PhD Oral Exam
Fri, Apr 27, 2018
Leavitt Path Superalgebras Katie Radler, SLU
Annual Awards Ceremony
Fri, Apr 27, 2018
The 2018 Math & Statistics Department Award Ceremony Featuring Sarah Greenwald, Appalachian State University
Previous events…
Upcoming events…