Zdenek Dvorak, Charles University, Czech Republic
Jan Kara, Charles University, Czech Republic
Daniel Kral, Charles University, Czech Republic
Jeffry Kahn, Math (Faculty)
Ondvrej Pangrac, Charles University (Graduate/Postdoc)
A t-cycle system is a system of cyclically ordered t-tuples of a finite set.
A pattern is a sequence of letters. A coloring of a t-cycle system
with respect to a set of patterns of length t is proper iff each cycle is
colored consistently with one of the patterns, i.e. the same/distinct letters
correspond to (the) same/distinct color(s).
For all combinations of P and k, we either find a polynomial algorithm or
prove NP-completeness of the problem whether a given cycle system with a set
of patterns P can be colored by at most k colors.
Ricardo Collado, University of Puerto Rico
Daniel Krasner, University of California, Berkeley, CA
Endre Boros, RUTCOR
Vladimir Gurvich, RUTCOR
Alexander Kelmans, University of Puerto Rico
Dorea Claassen, University of Nebraska, Lincoln, NE
Dr. Wilma Olson, Chemistry
Dr. Ilya Muchnik, DIMACS
With complete three-dimensional structural data it is possible to
understand which amino acids in a protein lie along that protein's surface
and how the surface of the protein is shaped. This, in turn, provides
information about protein function as proteins usually interact with other
molecules along their surfaces. Analysis of the surface can provide
information about where the protein is most likely to form bonds with
ligands and what sort of bonds it might form. However, If only the
sequence of amino acids for a protein is known, it is difficult to say
which amino acids will likely be on the surface of the protein, how that
particular protein might interact, or functions that protein might perform
in the cell. Our research seeks to develop models about protein/DNA
interaction capable of predicting some of these characteristics based only
on the protein's primary structure. We are developing our model using
protein/DNA complexes for which complete structural data is already known.
We will examine features of the protein structures as well as attributes
of the DNA itself at the binding sites in terms of the primary structure
of the protein in an attempt to develop predictive power about proteins
for which structural data is not available.
Matthew Adereth, Carnegie Melon University, Pittsburgh, PA
Mahesh Viswanathan, DIMACS
When analyzing a large stream of data it is often impractical to store all
of the input for later processing. To solve this problem, algorithms that
process the data stream as it is received, called Streaming Algorithms,
are used. I will be discussing techniques for analyzing lower bounds on
the memory usage of these algorithms.