Transcript Small World Networks

If I had to start all over
again...
Conference Honoring Louis Bolliet
May 2008
Jacques Cohen
Brandeis University
Waltham,MA
Environment at IMAG in
the early sixties
• Excitement about Computer Science
• Small cohesive research groups
• Freedom to engage in novel areas
• Easiness of interaction with French and
European researchers
• Abundance of resources
Contents
Research
• Systems and Synthetic Biology
• Social and Technological Networks
Education
• New Intro Course in CS (MIT)
Strong Interdisciplinary
Components
• Biology
• Physics
• Economics
• Sociology
• Emphasize Generalization over
Specialization
The Crucial Role of Systems-andSynthetic Biology in Computer
Science
DNA (Static) Bioinformatics
Deals mostly with sequences and
spatial structures (geometry)
DNA (Dynamic) Systems Biology
Deals with gene interactions:
graphs and dynamic systems
The seminal work of Jacob, Monod, Lwoff
Similarity between Computer Programs and
Regulatory Networks
Source Y. Yemini (YY) Computer Science Department
Columbia University
Theoretical Foundations
• Solution of systems of differential equations
(These equations can be rendered discrete)
• There is a fascinating theory linking genetic
•
networks (graphs) to the behavior of the
differential equations.
The theory was conjectured by Thomas
(Brussels) and proved by Soule´ (Bures-surYvette)
There are excellent teams in France
doing research on Genetic Networks,
Among them:
• Hidde de Jong (INRIAlpes)
• Hans Geiselmann (U Joseph Fourier)
• François Fages (INRIA, Paris)
• Denis Thieffry (Marseille)
• Gilles Bernot (Nice)
• Laurent Trilling (Grenoble)
• Jacques Nicolas (Rennes)
How to analyze and design new
regulatory networks
• In Synthetic Biology we want to design
new circuits (gene networks), insert them
in a cell and use the cell´s “operating
system” to carry out the execution, i.e.
produce a substance or effect.
• To do this let us to go back to sequencing
and synthesis of DNA
Sequencing Costs
• 2003- Human Genome Project ($3 billion)
• 2007- James Watson Genome ($1 million)
• 2008- Applied Bio-Systems ($60,000)
• 2011- Estimated ($1,000)
The $100 sequencing is
achievable sooner than anticipated
Complete Genomics and BioNanometrix
(MIT Tech Review April 17 2008)
BioNanometrix Chip (April 2008)
Advantages of inexpensive human
genome sequencing
• Detection of Single Nucleotide Polymorphisms
•
•
(SNP) done at doctor´s office
Selecting the best medication for a particular
patient
Personalized medicine
Dangers
• Breaches in privacy
• Ethical considerations
DNA Synthesis
C
A
ACCGTA ...
ComputerSynthesizer
G
T
Synthesis of DNA
• Related to sequencing (to check for accuracy)
• Design of minimal living artificial
organisms
• The 582,970 base pair M. genitalium
bacterial genome is the largest chemically
defined structure synthesized in Craig
Venter´s lab. (Water-marks have been added)
The mint-banana experiment
(a very informal description)
Steps
• Find somewhere (in a plant) a gene GM that
•
•
•
•
•
generates a product that smells like mint
Also find a gene GB capable of producing a
product that smells like bananas
Design a substance that can inhibit GM and
activate GB
Make sure that the process is robust
Place the combined genes, activators and
inhibitors in a cell and…
DEBUG!!!
Lofty Goals for Synthetic Biology
•
•
•
•
•
Detecting dangerous substances
Drug design
Cleaning oil spills
Eliminating CO2 in the atmosphere
Produce new fuels using e-coli or yeast
Synthetic Biology has its Dangers
• Bio-hacking
• Harmful forms of life (introduce the suicide gene for
safety)
France´s own synthetic-biology group
• In 2007 a team of young French researchers
•
•
won the first prize on basic research at the iGEM
competition (MIT)
iGEM -The international Genetically Engineered
Machine competition
Gregory Batt (former doctoral student of Hidde de
Jong, INRIAlpes) and Aurelien Rizk (doctoral
student of Francois Fages, INRIA) were key
partcipants.
Highly Recommended URLs
Craig Venter´s video
http://biosingularity.wordpress.com/category/synthetic-biology/
Article about Venter´s effort in Scientific American
http://www.sciam.com/article.cfm?id=longest-piece-of-dna-yet
Contents
Research
• Systems and Synthetic Biology
• Social and Technological Networks
Education
• New Intro Course in CS (MIT)
Trends in Obesity in the US
• Animation New England Journal of
Medicine
• http://content.nejm.org/cgi/content/full/357/4/370/DC2
Some key researchers
(It may all have started with Paul Erdos)
• Jon Kleinberg (Computer Scientist, Cornell)
• Mark Newman (Physicist, Santa Fe Institute)
• Albert-László Barabási (Physicist, biologist,
visiting Harvard)
• Duncan Watts (Sociologist, Columbia University)
• Steven Strogartz (Applied Math, Cornell)
• Mark Granovetter (Sociologist, Stanford)
Dynamics of Networks
Small World Networks (1)
Watts & Strogatz (Nature 1998)
Alternative Model of Small World
Laws that may govern networks
• Small world paradigm
• Power law
• Law of weak ties
Liben-Lowell Kleinberg
Tracing Information flow on a global scale
Chain Letters PNAS March 2008
Liben-Lowell Kleinberg (cont 1)
Chain letters
Liben-Lowell Kleinberg (cont 2)
Chain letters
Liben-Lowell Kleinberg (cont 3)
Chain letters
Final Result
• It is possible to determine the parameters
for generating trees that mimic very well
the behavior of the spread of chain letters.
• It is not a small-world behavior
Highly Recommended URLs
• Course in Finland (freely downloadable)
http://www.cis.hut.fi/Opinnot/T-61.184/
• Cornell Course by Kleinberg and Easley
http://www.infosci.cornell.edu/courses/info204/2007sp/
• In France LaBRI (Bordeaux) has a group working on
social networks
Contents
Research
• Systems and Synthetic Biology
• Social and Technological Networks
Education
• New Intro Course in CS (MIT)
MIT’s curriculum revision in EE
and CS
Hal Abelson
http://courses.csail.mit.edu/6.01/
research.google.com/university/relations/eduSummit2007/HalAbelson.pdf
10000
9000
8000
7000
6000
Number of MIT
Domestic Applicants
5000
4000
3000
2000
1000
0
2001
2002
2003
2004
2005
2006
2007
35%
30%
Percentage of
applicants indicating
interest in EE or CS
25%
20%
15%
10%
5%
0%
2001
2002
2003
2004
2005
2006
2007
New EECS Educational
Initiatives
• Increase integration of life
sciences and quantum
concepts into EECS
Similar to introduction of math
in early ‘50s and solid-state
physics in early ‘60s
• Restructure/renovate the
undergraduate curriculum
– Reduce the size of the common
core so as to increase depth and
add flexibility
– Current structure is 30 years old
– Two core subjects rather than
four
New Pedagogical Style
• Drastic decrease in lecture time
in favor of supervised labs
• Labs are more open ended
– Most labs involve mobile
robots
• Small student/staff ratio –
we’re aiming for 4:1
• In steady state, a substantial
fraction of undergrads will have
had teaching experience. This
is a design goal of the
curriculum reform.
Labs
• Programming in Python
• Applications to mobile robots
• Circuits on breadboards, connected to robot
Dealing with uncertainty
• Labs
• Concepts
– discrete probability
and state estimation
– abstracting continuous
probability models
– search, dynamic
programming
– state estimation in
simulated discrete
worlds
– robot localization
based on noisy sonar
– robot path planning
and execution
Grand finale: locate lights in a
maze using head, light sensors,
analog and digital control, state
estimation, and planning
Final Exam: Question 1
Imagine you have a simple robot with two wheels, each of
which has its own motor, and two photo-resistors.
1. Describe a strategy for driving the robot up to a light,
2.
3.
4.
by controlling the wheel velocities depending on the
photo-resistor values.
Assume the motors and photo-resistors are connected
to your computer, so that you can read and control
them in software. Write a step function in Python that
implements your strategy.
Design an analog circuit that does the whole job by
itself. Explain your strategy in English.
Describe the relative advantages and disadvantages of
these two solution strategies.
Conclusion
• The described areas share the following:
• Huge data sets
• Data integration is a must
• Work is inherently interdisciplinary
• Generality gains over Specialization
• Return to continuous models
• Important role of probability and statistics
Good News!
• Plenty of exciting new work for young
researchers.
• Exploring new areas is easier and (for
many of us) more fulfilling than deepening
into well known paths.
• Thank you!
Small World Networks (2)
Watts & Strogatz (Nature 1998)