|
|
-
In collaboration with the Center for
Computational Biology and Bioinformatics and,
in particular, its codirector,
Tandy Warnow,
at the University of Texas, I am
working on several projects in computational biology -- all
involving phylogeny reconstruction: given molecular or gene data
about a collection of organisms and a model of evolution, construct
the evolutionary tree for these organisms that most closely fits the
model. This is an extremely difficult computational problem,
complicated by a number of biological considerations.
Many algorithms have been designed by biologists and computer
scientists, but few have been rigorously analyzed and compared.
Moreover, most of the work has been done for molecular data (DNA
sequences or amino-acid sequences), with little done so far on the
emerging whole-genome approach, where each organism is described
by its gene sequence(s).
We are working with both types of data, conducting very large experiments
(the current set has been running for over 10 weeks on 40 computers...),
attempting to harness parallel computing, and also designing new algorithms.
We have a large collection of papers on the topic -- see my list
of papers from the front page. This project is supported at UNM by
three separate grants from the National Science Foundation,
EIA-01-21377,
EIA 01-13095,
and DEB-01-20709.
-
Under grant
ITR 00-81404
from the National Science Foundation, I am working with
David Bader on developing efficient parallel algorithms for
shared-memory machines (such as SMPs). The grant supports
3 graduate research assistants and 2 undergraduate researchers;
other research assistants participate under other sources of funding.
The research was greatly assisted by a grant from
Sun Microsystems,
combined with money from the Department of Computer Science's
NSF Infrastructure grant EIA 95-03064,
that allowed us to acquire a 14-processor, 14GB, shared-memory
Sun Enterprise E4500,
which has been our main research platform ever since.
-
I collaborate with Madhav Marathe of Los Alamos Laboratories
on various approximation problems in computational geometry.
One problem is automatic map
labeling: given point, line, and area features, how can the largest
possible labels be placed so as not to obscure the features and
observe some basic aesthetic criteria? In a recent SODA paper,
our PhD student Srinivas Doddi and we presented provably good
heuristics, both
in the worst-case and in a randomized setting. Our approaches
rely on the solution of k-nearest-neighbor problems in the plane.
(An implementation is under way, thanks to one of my MS students,
Jim Tanzola.)
Another problem arises from mobile computing: partition
and allocation problems among nodes and edges of a connectivity graph.
Preliminary results indicate that provably good heuristics are also
possible for this problem.
-
As part of my work as Editor-in-Chief of the
ACM Journal of Experimental
Algorithms, I am working with the ACM and with colleagues
around the world in developing mechanisms for sharing data, instance
generators, code, etc. Since the JEA is also ACM's first on-line
journal, developing its mechanisms has been another task, which is
reviewed in a recent article in the
Journal of
Electronic Publishing.
|