In this talk, I will discuss several geometric tiling and packing problems in one or more dimensions that have applications to several areas such as nonoverlapping local alignments, DNA microarray designs and homology searches in database. For example, a typical problem considered is to find a set of "independent" rectangles of total maximum weight giving a a set of local alignments between two DNA sequences. Our main goal is to design linear or near-linear time exact or approximation algorithms for these problems.
(Joint works with one or more of the following persons: Piotr Berman, Paul Bertone, Mark Gerstein, Ming-Yang Kao, S. Muthukrishnan, Michael Snyder)