IMADA - Department of Mathematics and Computer Science |
We consider the problem of BLASTing a genome against a database of DNA sequences to see whether the genome has subsequences in common with known genomes. We consider a setting where the problem is distributed to PCs having idle time. This results in an equivalent bin packing problem, where a rectangle is divided into smaller rectangles that are to be packed in variable-sized bins which arrive on-line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle. Joint work with Joan Boyar. Host: Joan Boyar SDU HOME | IMADA HOME | Previous Page Last modified: Mon Jan 14 09:32:50 CET 2008 Joan Boyar (joan@imada.sdu.dk) |