CSP
Seminar Abstracts
(see schedule
for a list of talks)
Spring
2000
2:10-3:00,
Thursdays
353
Durham
3/30/00
CSP
Talk Canceled
Go to
Distinguish Lecture
RICHARD M. KARP
THURSDAY - MARCH 30, 2000
Lecture:
Reception:
MOLECULAR BIOLOGY BLDG. ROOM 1414
********************************************************************
Sponsored by: Cargill and
Miller Lecture Funds
Abstract
A fundamental
problem in molecular biology is to determine how genes and
proteins work
in concert to control the functioning of living cells. This
talk will be a
survey of algorithmic approaches to this problem, drawn from
the fields of
combinatorial optimization, statistics, machine learning,
dynamical
systems and stochastic simulation.
Proteins are
the active elements that perform cellular functions. Proteins
are
manufactured by transcribing genes into mRNA and then translating mRNA
into protein.
The rates at which specific transcription and translation
processes take
place depend on the environment of the cell and on the
abundances and
spatial distribution of different species of mRNA and
protein. Thus
the cell can be viewed as a complex feedback control system.
The DNA
microarray is a recently developed tool capable of measuring the
transcription
rates of thousands of genes in a single experiment. Technology
is being
developed to measure large numbers of protein abundances in a
single
experiment. Such high-throughput experimental tools will give a
panoramic view
of the state of a tissue or collection of cells. By measuring
transcription
one can distinguish normal tissue from neoplastic tissue, or
cells treated
with a drug from untreated cells. By measuring the effects of
artificially
inducing or inhibiting the transcription of particular genes
one can explore
the structure of genetic regulation.
This talk will
be concerned with the acquisition and interpretation of large
scale gene
expression data. We will discuss algorithms for clustering or
classifying
tissues on the basis of their gene expression patterns, as well
as algorithms
to efficiently learn the structure of genetic regulatory
networks on the
basis of judiciously chosen experiments.
*********************************************************************
Richard M. Karp
was born in Boston, Massachusetts in 1935 and was educated
at the Boston
Latin School and Harvard University, where he received the
Ph.D. in
Applied Mathematics in 1959. From 1959 to 1968 he was a member of
the
Mathematical Sciences Department at the IBM Thomas J. Watson Research
Center. From
1968 to 1994 he was a Professor of Computer Science,
Mathematics and
Operations Research at the University of California,
Berkeley. From
1988 to 1995 he was also associated with the International
Computer
Science Institute (ICSI) in Berkeley. In 1995 he became a Professor
of Computer
Science and Engineering and an Adjunct Professor of Molecular
Biotechnology
at the University of Washington. This summer he will return to
Berkeley as a
University Professor. His principal appointment will be in
Computer
Science, and he will also hold appointments in Mathematics and
Bioengineering.
In addition, he will again be a research scientist at ICSI.
The unifying
theme in Karp's work has been the study of combinatorial
algorithms. His
most significant work is the 1972 paper ``Reducibility Among
Combinatorial
Problems,'' which shows that many of the most commonly studied
combinatorial
problems are disguised versions of a single underlying
problem, and
thus are all of essentially the same computational complexity.
Much of his
subsequent work has concerned the development of parallel
algorithms, the
probabilistic analysis of combinatorial optimization
problems, and
the construction of randomized algorithms for combinatorial
problems. His
current research is concerned with strategies for sequencing
the human
genome, the physical mapping of large DNA molecules, the analysis
of gene
expression data, and other combinatorial problems arising in
molecular
biology.
Karp has
received the U.S. National Medal of Science, the Harvey Prize
(Technion), the
Turing Award (ACM), the Centennial Medal (Harvard
University) the
Fulkerson Prize(AMS and Math. Programming Society), the von
Neumann Theory
Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann
Lectureship
(SIAM) and the Distinguished Teaching Award (Berkeley). He is a
member of the
National Academy of Sciences, the National Academy of
Engineering and
the American Philosophical Society, as well as a Fellow of
the American
Academy of Arts and Sciences. He holds four honorary degrees.
*********************************************************
3/23
Intrusion Detection: An Audit Trial Method
Bin Shao
Abstract
As modern computer networks are
vulnerable to malicious activities such as
unauthorized access to private
data, denial of service, and unauthorized
intrusions, intrusion detection
methods are becoming more important. There
are generally two branches in
intrusion detection methods: recognize known
attacks and detect new
intrusions. Knowledge bases are required to compare
the intrusion signatures with the
stored patterns for the first method, in
order to adapt to new attacks,
learning methods must be applied to update
the tendency and performance of
the system. In this project, an neural
network is constructed as the
system base architecture, an reinforcement
learning method is employed as
training algorithm and a sliding window is
used to adapt to new changes.
This system is currently being developed to
detect system performance
anomalies.
3/2
A Hybrid Neural Network / Nearest Neighbor Modeling
Approach
Craig Carmichael
Abstract
Artificial Neural Networks have been shown to be capable of
modeling a large class of problems, usually resulting in good generalization.
Nearest neighbor algorithms, however, still outperform ANNs on some modeling
problems. Presented is an approach to combine the strengths of both methods
into a single algorithm, called the neural neighbors algorithm (NNA).
Preliminary work suggests that a hybrid approach can outperform either one in
terms of generalization, on at least a subclass of problems. The NNA method is
currently being developed to automatically find the optimal balance of the two
approaches for any given data set. This should increase the scope of the
method's usefulness across a wider range of modeling problems.
2/24
Dynammic Node Architecutre: An Information
Theoretic Approach
Varma Dantuluri
Abstract
Typically Artificial Neural Network training schemes require
network size to be set before learning is initiated. The learning
speed and generalization characteristics of ANNs are, however, dependent
on this pretraining selection of the network architecture. The training
and generalization viability of a specific network can, therefore, only
be evaluated posttraining. This work presents an Information Theoretic
method that alleviates this predicament by building the appropriate
network architecture dynamically during the training process. The
method, called Dynammic Node Architecture Learning (DNAL), eliminates
the need to select network size before training.
2/17
Modeling of Wideband CDMA Draft
Specifications
Hemlata Ahir
Code Division Multiple Access (CDMA)
is a technique in which the separation between users is acheived by
orthogonality among the user codes. It involves spread spectrum modulation of
the information signal resulting in a substantially increased bandwidth as
compared to the information bandwidth itself. This basic principle with its
numerous advantages has been adopted in CDMA systems such as IS-95 which has
been accepted as a standard for second generation mobile systems. The keypoints
of the IS-95 system will be discussed in this seminar. Also, a brief
introduction to the third generation systems based on Wideband CDMA (WCDMA)
will be provided followed by a discussion of modeling it based upon its draft
specifications for the purposes of further research.
Last updated March 30, 2000