Seeing Like a Baby

English

Infants soon learn to make sense of the complex world around them: Their understanding far surpasses any of the current attempts to design intelligent computerized systems. How do such young infants arrive at this understanding?

 

Answering this question has been a challenge for cognitive psychology researchers and computer scientists alike. On the one hand, babies cannot explain how they first learn to comprehend the world around them, and on the other, computers, for all their sophistication, need human help with labeling and sorting objects to make learning possible.  Many scientists believe that for computers to “see” the world as we do, they must first learn to classify and identify objects in much the same way that a baby does.
 

Mover event detected in the red cell: Motion (left) flows into the cell, (middle) stays briefly in the cell, and (right) leaves the cell, changing its appearance. Warmer colors indicate faster motion
 
 
 
 
 
 
 
 
 
Prof. Shimon Ullman and research students Daniel Harari and Nimrod Dorfman of the Institute’s Computer Science and Applied Mathematics Department set out to explore the learning strategies of the young brain by designing computer models based on the way that babies observe their environment. The team first focused on hands: Within a few months, babies can distinguish a randomly viewed hand from other objects or body parts, despite the fact that hands are actually very complex – they can take on quite a range of visual shapes and move in different ways. Ullman and his team created a computer algorithm for learning hand recognition. The aim was to see if the computer could learn independently to pick hands out of video footage – even when those hands took on different shapes or were seen from different angles. That is, nothing in the program said to the computer: “Here is a hand.” Instead, it had to discover from repeated viewing of the video clips what constitutes a hand.

The algorithm began with some basic insight into the stimuli that attract the attention of young infants. The scientists knew, for instance, that babies track movement from the moment they open their eyes, and that motion can be a visual cue for picking objects out of the scenery. The researchers then asked if certain types of movement might be more instructive to the infant mind than others, and whether these could provide enough information to form a visual concept. For instance, a hand makes a change in the baby’s visual field, generally by manipulating an object. Eventually the child might extrapolate, learning to connect the idea of causing-object-to-move with that of a hand. The team named such actions “mover events.”
 
 
Predicted direction of gaze: results of algorithm (red arrows) and two human observers (green arrows). Faces, top to bottom, belong to Prof. Shimon Ullman, Daniel Harari and Nimrod Dorfman
 
After designing and installing an algorithm for learning through detecting mover events, the team showed the computer a series of videos. In some, hands were seen manipulating objects. For comparison, others were filmed as if from the point of view of a baby watching its own hand move, or else movement that did not involve a mover event, or typical visual patterns such as videos of common body parts or people. These trials clearly showed that mover events – watching another’s hand move objects – were not only sufficient for the computer to learn to identify hands, they far outshone any of the other methods, including that of “self-movement.”

But the model was not yet complete. With mover events, alone, the computer could learn to detect hands but still had trouble with different poses. Again, the researchers went back to insights into early perception: Infants can not only detect motion, they can track it; they are also very interested in faces. Adding in mechanisms for observing the movements of already detected hands to learn new poses, and for using the face and body as reference points to locate hands, improved the learning process.

In the next part of their study, the researchers looked at another, related concept that babies learn early on but computers have trouble grasping – knowing where another person is looking. Here, the scientists took the insights they had already gained – mover events are crucial and babies are interested in faces – and added a third: People look in the direction of their hands when they first grasp an object. On the basis of these elements, the researchers created another algorithm to test the idea that babies first learn to identify the direction of a gaze by connecting faces to mover events. Indeed, the computer learned to follow the direction of even a subtle glance – for instance, the eyes alone turning toward an object – nearly as well as an adult human.

The researchers believe these models show that babies are born with certain pre-wired patterns – such as a preference for certain types of movement or visual cues. They refer to this type of understanding as proto-concepts – the building blocks with which one can begin to build an understanding of the world. Thus the basic proto-concept of a mover event can evolve into the concept of hands and of direction of gaze, and eventually give rise to even more complex ideas such as distance and depth.

This study is part of a larger endeavor known as the Digital Baby Project. The idea, says Harari, is to create models for very early cognitive processes. “On the one hand,” says Dorfman, “such theories could shed light on our understanding of human cognitive development. On the other hand, they should advance our insights into computer vision (and possibly machine learning and robotics).” These theories can then be tested in experiments with infants, as well as in computer systems.
 
Prof. Ullman is the incumbent of the Ruth and Samy Cohn Professorial Chair of Computer Sciences.





 
 


 

Mover event detected in the red cell: Motion (left) flows into the cell, (middle) stays briefly in the cell, and (right) leaves the cell, changing its appearance. Warmer colors indicate faster motion
Math & Computer Science
English

Weizmann Invention: Visual Summarization

English
 
 
Prof. Michal Irani
 
Yeda Research and Development, Ltd., the commercial arm of the Weizmann Institute of Science, recently entered into a license agreement with Adobe Systems Incorporated related to a bidirectional similarity measure to summarize visual data.
 
The bidirectional similarity method developed by Prof. Michal Irani and Drs. Denis Simakov, Yaron Caspi and Eli Shechtman of the Institute’s Computer Science and Applied Mathematics Department can be used on both still images and videos. The method produces a complete and coherent visual summary – a smaller or shorter version of the original that retains the most relevant information. The bidirectionality of the method ensures that the resulting image is visually coherent: In addition to telling the same “story,” it is as visually satisfying as the original. As opposed to cropping or clipping, in which important information can be lost; or scaling down, in which resolution is lost, summarizing manages to maintain relevant information as well as resolution details, despite the decrease in size. 
 

The method is based on eliminating redundant information from the image/video. Video summarization works in a similar way, except that the program exploits redundancy in space-time. Gradual resizing and rechecking ensures that the final result is seamless and coherent.



In addition to summarizing images and videos, the method may have a number of other applications: completing missing parts in images/videos; creating montages out of separate images; photo reshuffling (in which elements in the image/video can be moved around); automatic cropping; image synthesis (in which an image can be expanded, rather than summarized); and image morphing (generating a video sequence that displays a smooth transition from one image to another, possibly unrelated, image).

Prof. Michal Irani's research is supported by the Citi Foundation.

 
 

(l-r) Before and after images showing summarization with the bidirectional similarity measure. All of the relevant visual information is preservedsummarized image

 


Original video

 


Summarized video

 

 

The "Before image" of Visual Summarization
Math & Computer Science
English

Encryption while You Work

English
 
As computer data moves to the “cloud” – networks of shared, remote servers – security becomes more of a challenge. Ideally, users should be able to perform operations on their data with complete confidence that no one can peek over their virtual shoulders.
 
Prof. Shafi Goldwasser and Dr. Zvika Brakerski
 
Research carried out at the Weizmann Institute and MIT is moving us closer to the ability to work on data while it is still encrypted, giving an encrypted result that can later be securely deciphered.

“Until a few years ago, no one knew if the encryption needed for this sort of online security was even possible,” says Dr. Zvika Brakerski, who recently completed his Ph.D. in the group of Prof. Shafi Goldwasser of the Computer Science and Applied Mathematics Department. In 2009, the first so-called fully homomorphic encryption (FHE) was demonstrated.

That early version of fully homomorphic encryption was time-consuming and unwieldy. But Brakerski, together with Dr. Vinod Vaikuntanathan (who was a student of Goldwasser’s at MIT), surprised the computer security world last year with two papers in which they described several new ways of making fully homomorphic encryption more efficient. They not only simplified the arithmetic, speeding up processing time, but showed that a mathematical construct called an ideal lattice, used to generate the encryption keys, could be simplified without compromising security.
 
Their result promises to pave a path to applying FHE in practice.  Optimized versions of the new system could be hundreds – or even thousands – of times faster than the original construction. Indeed, Brakerski and Vaikuntanathan have managed to advance the theory behind fully homomorphic encryption to the point that computer engineers can begin to work on applications.
 
Prof. Shafrira Goldwasser’s research is supported by Walmart.

 
 
Prof. Shafi Goldwasser and Dr. Zvika Brakerski
Math & Computer Science
English

YEDA Collaborates with Adobe for New Data Visualization Technique

English
YEDA Research and Development Company LTD., the commercial arm of the Weizmann Institute of Science, today announced it has entered into a license agreement with Adobe Systems Incorporated related to a bidirectional similarity measure to summarize visual data.

The bidirectional similarity method developed by Prof. Michal Irani and Drs. Denis Simakov, Yaron Caspi and Eli Shechtman of the Institute’s Computer Science and Applied Mathematics Department is a technique for summarizing visual data – both still images and video. Rather than cropping or scaling down an image to obtain a smaller thumbnail, or clipping a video segment, the method produces a complete and coherent visual summary: a smaller or shorter version of the original that retains the most relevant information. The bi-directionality of the method ensures that the resulting image is visually coherent: In addition to telling the same “story,” it is as visually pleasing as the original. As opposed to cropping or clipping, in which important information can be lost; or scaling down, in which resolution is lost, summarizing manages to maintain both relevant information and resolution details, despite the decrease in size.   

The method is based on eliminating redundant information from the image/video. Video summarization works in a similar way, only the program exploits redundancy in space-time. Gradual resizing and rechecking ensures that the final result is seamless and coherent.

In addition to summarizing images and videos, the method may have a number of other applications, including completing missing parts in images/videos; creating montages out of separate images; photo reshuffling (in which elements may be moved around the image/video); automatic cropping; image synthesis (in which an image might be expanded, rather than summarized); and image morphing (generating a video sequence displaying a smooth transition from one image to another, possibly unrelated, image).
 
(l-r) Before and after images showing summarization with the bidirectional similarity measure. All of the relevant visual information is preserved
 

 


Source video

 

 


Summary video

 

 

Prof. Michal Irani’s research is supported by the Citi Foundation.

Yeda Research and Development Company Ltd. is the Technology Transfer Company of the Weizmann Institute of Science. Yeda markets and commercializes intellectual property created in the Weizmann Institute laboratories.

 
(l-r) Before and after images showing summarization with the bidirectional similarity measure. All of the relevant visual information is preserved
Math & Computer Science
English

Improving Security in the Cloud

English
Less and less of today’s computing is done on desktop computers; cloud computing, in which operations are carried out on a network of shared, remote servers, is expected to rise as the demand for computing power increases. This raises some crucial questions about security: Can we, for instance, perform computations on data stored in “the cloud” without letting anyone else see our information? Research carried out at the Weizmann Institute and MIT is moving us closer to the ability to work on data while it is still encrypted, giving an encrypted result that can later be securely deciphered.

Attempting computation on sensitive data stored on shared servers leaves that data exposed in ways that traditional encryption techniques can’t protect against. The main problem is that to manipulate the data, it has to be first decoded. “Until a few years ago, no one knew if the encryption needed for this sort of online security was even possible,” says Dr. Zvika Brakerski, who recently completed his Ph.D. in the group of Prof. Shafi Goldwasser of the Computer Science and Applied Mathematics Department. In 2009, however, a Ph.D. student at Stanford University named Craig Gentry provided the first demonstration of so-called fully homomorphic encryption (FHE). But the original method was extraordinarily time consuming and unwieldy, making it highly impractical. Gentry constructed his FHE system by using fairly sophisticated math, based on so-called ideal lattices, and this required him to make new and unfamiliar complexity assumptions to prove security. Gentry’s use of ideal lattices seemed inherent to fully homomorphic encryption; researchers assumed that they were necessary for the server to perform such basic operations as addition and multiplication on encrypted data.

Brakerski, together with Dr. Vinod Vaikuntanathan (who was a student of Goldwasser’s at MIT), surprised the computer security world earlier this year with two recent papers in which they described several new ways of making fully homomorphic encryption more efficient. For one thing, they managed to make FHE work with much simpler arithmetic, which speeds up processing time. And a surprise discovery showed that a mathematical construct used to generate the encryption keys could be simplified without compromising security. Gentry’s original ideal lattices are theoretical collections of points that can be added together – as in an ordinary lattice structure – but also multiplied. But the new research shows that the lattice does not have to be ideal, which simplifies the construction immensely.  “The fact that it worked was something like magic, and it has challenged our assumptions about the function of the ideal lattices in homomorphic encryption,” says Brakerski.

Their result promises to pave a path to applying FHE in practice. Optimized versions of the new system could be hundreds – or even thousands – of times faster than Gentry’s original construction. Indeed, Brakerski and Vaikuntanathan have managed to advance the theory behind fully homomorphic encryption to the point that computer engineers can begin to work on applications. These might include, for instance, securing medical information for research: A third party could perform large medical studies on encrypted medical records without having access to the individuals’ information.  
 
Prof. Shafrira Goldwasser’s research is supported by Walmart.


 
Math & Computer Science
English

DNA Computation Gets Logical at the Weizmann Institute of Science

English
Biomolecular computers, made of DNA and other biological molecules, only exist today in a few specialized labs, remote from the regular computer user. Nonetheless, Tom Ran and Shai Kaplan, research students in the lab of Prof. Ehud Shapiro of the Weizmann Institute’s Biological Chemistry, and Computer Science and Applied Mathematics Departments have found a way to make these microscopic computing devices ‘user friendly,’ even while performing complex computations and answering complicated queries.
 

Shapiro and his team at Weizmann introduced the first autonomous programmable DNA computing device in 2001. So small that a trillion fit in a drop of water, that device was able to perform such simple calculations as checking a list of 0s and 1s to determine if there was an even number of 1s. A newer version of the device, created in 2004, detected cancer in a test tube and released a molecule to destroy it. Besides the tantalizing possibility that such biology-based devices could one day be injected into the body – a sort of ‘doctor in a cell’ locating disease and preventing its spread – biomolecular computers could conceivably perform millions of calculations in parallel.
 
Now, Shapiro and his team, in a paper published online today in Nature Nanotechnology, have devised an advanced program for biomolecular computers that enables them to ‘think’ logically. The train of deduction used by this futuristic device is remarkably familiar. It was first proposed by Aristotle over 2000 years ago as a simple if…then proposition: ‘All men are mortal. Socrates is a man. Therefore, Socrates is mortal.’ When fed a rule (All men are mortal) and a fact (Socrates is a man), the computer answered the question ‘Is Socrates Mortal?’ correctly. The team went on to set up more complicated queries involving multiple rules and facts, and the DNA computing devices were able to deduce the correct answers every time.
 
At the same time, the team created a compiler – a program for bridging between a high-level computer programming language and DNA computing code. Upon compiling, the query could be typed in something like this: Mortal(Socrates)?. To compute the answer, various strands of  DNA representing the rules, facts and queries were assembled by a robotic system and searched for a fit in a hierarchical process. The answer was encoded in a flash of green light: Some of the strands had a biological version of a flashlight signal – they were equipped with a naturally glowing fluorescent molecule bound to a second protein which keeps the light covered. A specialized enzyme, attracted to the site of the correct answer, removed the ‘cover’ and let the light shine. The tiny water drops containing the biomolecular data-bases were able to answer very intricate queries, and they lit up in a combination of colors representing the complex answers.


Prof. Ehud Shapiro’s research is supported by the Clore Center for Biological Physics; the Arie and Ida Crown Memorial Charitable Fund; the Phyllis and Joseph Gurwin Fund for Scientific Advancement; Sally Leafman Appelbaum, Scottsdale, AZ; the Carolito Stiftung, Switzerland; the Louis Chor Memorial Trust Fund; and Miel de Botton Aynsley, UK. Prof. Shapiro is the incumbent of the Harry Weinrebe Chair of Computer Science and Biology.

 

The Weizmann Institute of Science in Rehovot, Israel, is one of the world's top-ranking multidisciplinary research institutions. Noted for its wide-ranging exploration of the natural and exact sciences, the Institute is home to 2,600 scientists, students, technicians and supporting staff. Institute research efforts include the search for new ways of fighting disease and hunger, examining leading questions in mathematics and computer science, probing the physics of matter and the universe, creating novel materials and developing new strategies for protecting the environment.

 

Weizmann Institute news releases are posted on the World Wide Web at http://wis-wander.weizmann.ac.il, and are also available at http://www.eurekalert.org.

Math & Computer Science
English

Working Artificial Nerve Networks

English
Weizmann Institute Scientists Create Working Artificial Nerve Networks

Scientists have already hooked brains directly to computers by means of metal electrodes, in the hope of both measuring what goes on inside the brain and eventually healing conditions such as blindness or epilepsy. In the future, the interface between brain and artificial system might be based on nerve cells grown for that purpose. In research that was recently featured on the cover of Nature Physics, Prof. Elisha Moses of the Physics of Complex Systems Department and his former research students Drs. Ofer Feinerman and Assaf Rotem have taken the first step in this direction by creating circuits and logic gates made of live nerves grown in the lab.

When neurons – brain nerve cells – are grown in culture, they don’t form complex ‘thinking’ networks. Moses, Feinerman and Rotem wondered whether the physical structure of the nerve network could be designed to be more brain-like. To simplify things, they grew a model nerve network in one dimension only – by getting the neurons to grow along a groove etched in a glass plate. The scientists found they could stimulate these nerve cells using a magnetic field (as opposed to other systems of lab-grown neurons that only react to electricity).

Experimenting further with the linear set-up, the group found that varying the width of the neuron stripe affected how well it would send signals. Nerve cells in the brain are connected to great numbers of other cells through their axons (long, thin extensions), and they must receive a minimum number of incoming signals before they fire one off in response. The researchers identified a threshold thickness, one that allowed the development of around 100 axons. Below this number, the chance of a response was iffy, while just a few over this number greatly raised the chance a signal would be passed on.

The scientists then took two thin stripes of around 100 axons each and created a logic gate similar to one in an electronic computer. Both of these ‘wires’ were connected to a small number of nerve cells. When the cells received a signal along just one of the ‘wires,’ the outcome was uncertain; but a signal sent along both ‘wires’ simultaneously was assured of a response. This type of structure is known as an AND gate. The next structure the team created was slightly more complex: Triangles fashioned from the neuron stripes were lined up in a row, point to rib, in a way that forced the axons to develop and send signals in one direction only. Several of these segmented shapes were then attached together in a loop to create a closed circuit. The regular relay of nerve signals around the circuit turned it into a sort of biological clock or pacemaker.

Moses: ‘We have been able to enforce simplicity on an inherently complicated system. Now we can ask, ‘What do nerve cells grown in culture require in order to be able to carry out complex calculations?’ As we find answers, we get closer to understanding the conditions needed for creating a synthetic, many-neuron ‘thinking’ apparatus.’     

For the scientific paper, please see:  http://www.nature.com/nphys/journal/v4/n12/pdf/nphys1099.pdf
 
 
 
 
The Weizmann Institute of Science in Rehovot, Israel, is one of the world's top-ranking multidisciplinary research institutions. Noted for its wide-ranging exploration of the natural and exact sciences, the Institute is home to 2,600 scientists, students, technicians and supporting staff. Institute research efforts include the search for new ways of fighting disease and hunger, examining leading questions in mathematics and computer science, probing the physics of matter and the universe, creating novel materials and developing new strategies for protecting the environment.

Weizmann Institute news releases are posted on the World Wide Web at http://wis-wander.weizmann.ac.il/, and are also available at http://www.eurekalert.org/.
 
Math & Computer Science
English

A Better DNA Molecule

English

Weizmann Institute Scientists Build A Better DNA Molecule


Building faultless objects from faulty components may seem like alchemy. Yet scientists from the Weizmann Institute’s Computer Science and Applied Mathematics, and Biological Chemistry Departments have achieved just that, using a mathematical concept called recursion. 'We all use recursion, intuitively, to compose and comprehend sentences like ‘the dog that chases the cat that bit the mouse that ate the cheese that the man dropped is black,’' says Prof. Ehud Shapiro.


Recursion allows long DNA molecules to be composed hierarchically from smaller building blocks. But synthetic DNA building blocks have random errors within their sequence, as do the resulting molecules. Correcting these errors is necessary for the molecules to be useful. Even though the synthetic molecules are error prone, some of them are likely to have long stretches that do not contain any faults. These stretches of faultless DNA can be identified, extracted, and reused in another round of recursive construction. Starting from longer and more accurate building blocks in this round increases the chances of producing a flawless long DNA molecule. The team, led by doctoral students Gregory Linshiz and Tuval Ben-Yehezkel under the supervision of Shapiro, found in their experiments that two rounds of recursive construction were enough to produce a flawless target DNA molecule. If need be, however, the error correction procedure could be repeated until the desired molecule is formed.


The team’s research, recently published in the journal Molecular Systems Biology, provides a novel way to construct faultless DNA molecules with greater speed, precision, and ease of combining synthetic and natural DNA fragments than existing methods. 'Synthetic DNA molecules are widely needed in biological and biomedical research, and we hope that their efficient and accurate construction using this recursive process will help to speed up progress in these fields,' says Shapiro.

   
Prof. Ehud Shapiro’s research is supported by the Clore Center for Biological Physics; the Arie and Ida Crown Memorial Charitable Fund; the Cymerman - Jakubskind Prize; the Fusfeld Research Fund; the Phyllis and Joseph Gurwin Fund for Scientific Advancement; the Henry Gutwirth Fund for Research; Ms. Sally Leafman Appelbaum, Scottsdale, AZ; the Carolito Stiftung, Switzerland; the Louis Chor Memorial Trust Fund; and the estate of Fannie Sherr, New York, NY.  Prof. Shapiro is the incumbent of the Harry Weinrebe Chair of Computer Science and Biology.

 

 

 

The Weizmann Institute of Science in Rehovot, Israel, is one of the world's top-ranking multidisciplinary research institutions. Noted for its wide-ranging exploration of the natural and exact sciences, the Institute is home to 2,600 scientists, students, technicians and supporting staff. Institute research efforts include the search for new ways of fighting disease and hunger, examining leading questions in mathematics and computer science, probing the physics of matter and the universe, creating novel materials and developing new strategies for protecting the environment.

Weizmann Institute news releases are posted on the World Wide Web at
http://wis-wander.weizmann.ac.il/, and are also available at http://www.eurekalert.org/

 

Math & Computer Science
English

Switching Goals

English

A computer simulation shows how evolution may have speeded up

 

Is heading straight for a goal the quickest way there? If the name of the game is evolution, suggests new research at the Weizmann Institute of Science, the pace might speed up if the goals themselves change continuously.

 

Nadav Kashtan, Elad Noor and Prof. Uri Alon of the Institute’s Molecular Cell Biology and Physics of Complex Systems Departments create computer simulations that mimic natural evolution, allowing them to investigate processes that, in nature, take place over millions of years. In these simulations, a population of digital genomes evolves over time towards a given goal: to maximize fitness under certain conditions. Like living organisms, genomes that are better adapted to their environment may survive to the next generation or reproduce more prolifically. But such computer simulations, though sophisticated, don’t yet have all the answers. Achieving even simple goals may take thousands of generations, raising the question of whether the three-or-so billion years since life first appeared on the planet is long enough to evolve the diversity and complexity that exist today,

 

Evolution takes place under changing environmental conditions, forcing organisms to continually readapt. Intuitively, this would slow things down even further, as successive generations must switch tack again and again in the struggle to survive. But when Kashtan, Noor and Alon created a simulation in which the goals changed repeatedly, they found that its evolution actually speeded up. They even found that the more complex the goal – i.e., the more generations needed reach it under fixed conditions – the faster evolution accelerated in response to changes in that goal.

 

Computerized evolution ran fastest, the scientists found, when the changes followed a pattern they believe may be pervasive in nature. In previous research, Kashtan and Alon had shown that evolution may often be modular – involving adjustments to standard parts, rather than wholesale remodeling. They theorized that the forces acting on evolution may be modular as well, and for each goal, they defined subgoals that could each change in relation to the others. 'In an organism, for example, you might classify these subgoals as the need to eat, the need to keep from being eaten, and the need to reproduce. The same subgoals must be fulfilled in each new environment, but there are differences in nuance and combination,' says Kashtan. 'We saw a large speedup, for instance, when we repeatedly exchanged an 'OR' for an 'AND' in the computer code defining our goals, thus changing the relationship between subgoals.' 

 

Although the main aim of this research, which appeared recently in the Proceedings of the National Academy of Sciences (PNAS), was to shed light on theoretical questions of evolution, it may have some practical implications, particularly in engineering fields in which evolutionary tools are commonly used for systems design; and in computer science, by providing a possible way to accelerate optimization algorithms. 
  
Prof. Uri Alon’s research is supported by the Nella and Leon Benoziyo Center for Neurological Diseases; the Clore Center for Biological Physics; the Yad Abraham Research Center for Cancer Diagnostics and Therapy; the Leon and Gina Fromer Philanthropic Fund; the Kahn Family Foundation for Humanitarian Support; Keren Isra-Pa’amei Tikva Ltd.; the Minerva Stiftung Gesellschaft fuer die Forschung m.b.H.; the James and Ilene Nathan Charitable Directed Fund; the Harry M. Ringel Memorial Foundation; the estate of Ernst and Anni Deutsch, Liechtenstein; and Mr. and Mrs. Mordechai Segal, Israel.

 

The Weizmann Institute of Science in Rehovot, Israel, is one of the world's top-ranking multidisciplinary research institutions. Noted for its wide-ranging exploration of the natural and exact sciences, the Institute is home to 2,600 scientists, students, technicians and supporting staff. Institute research efforts include the search for new ways of fighting disease and hunger, examining leading questions in mathematics and computer science, probing the physics of matter and the universe, creating novel materials and developing new strategies for protecting the environment.

 

Weizmann Institute news releases are posted on the World Wide Web at http://wis-wander.weizmann.ac.il/, and are also available at http://www.eurekalert.org/.
Math & Computer Science
English

Lineage Trees for Cells

English

A multidisciplinary team at the Weizmann Institute of Science has developed an analytical method that can trace the lineage trees of cells

 

Some fundamental outstanding questions in science: 'Where do stem cells originate?' 'How does cancer develop?' 'When do cell types split off from each other in the embryo? 'might be answered if scientists had a way to map the history of the body's cells going back to the fertilized egg. Now, a multidisciplinary team at the Weizmann Institute of Science has developed an analytical method that can trace the lineage trees of cells.

 
This accomplishment started with a challenge to common wisdom, which says that every cell in an organism carries an exact duplicate of its genome. Although mistakes in copying, which are passed on to the next generation of cells as mutations, occur when cells divide, such tiny flaws in the genome are thought to be trivial and mainly irrelevant.  But research students Dan Frumkin, and Adam Wasserstrom of the Biological Chemistry Department, working under the guidance of Prof. Ehud Shapiro of the Institute's Biological Chemistry, and Computer Science and Applied Mathematics Departments, raised a new possibility: Though biologically insignificant, the accumulated mutations might hold a record of the history of cell division.
 
Together with Prof. Uriel Feige, of the Computer Science and Applied Mathematics Department, and research student Shai Kaplan, they proved that these mutations can be treated as information and used to trace lineage on a large scale, and then applied the theory to extracting data and drafting lineage trees for living cells.
 
Methods employed until now for charting cell lineage trees have relied on direct observation of developing embryos. This method worked well enough for the tiny, transparent worm, C. elegans, that has around 1000 cells, all told, but for humans, with 100 trillion cells, or even newborn mice or human embryos at one month, each of which has a billion cells after some 40 rounds of cell division, the task would be impossible.
 
The study focused on mutations in specific, mutation-prone areas of the genome known as microsatellites. In microsatellites, a genetic 'phrase' consisting of a few nucleotides(genetic 'letters') is repeated over and over; mutations manifest themselves as additions or subtractions in length. Based on the current understanding of the mutation process in these segments, the scientists proved mathematically that microsatellites alone contain enough information to accurately plot the lineage tree for a one-billion-cell organism.
 
Both human and mouse genomes contain around 1.5 million microsatellites, but the team's findings demonstrated that a useful analysis can be performed based on a much smaller number. To obtain a consistent mutation record, the team used organisms with a rare genetic defect found in plants and animals alike. While healthy cells have repair mechanisms to correct copying mistakes and prevent mutation, cells with the defect lack this ability, allowing mutations to accumulate relatively rapidly.
 
Borrowing a computer algorithm used by evolutionary biologists that analyzes genetic information in order to place organisms on branches of the evolutionary tree, the researchers assembled an automated system that samples the genetic material from a number of cells, compares it for specific mutations, applies the algorithm to assess degrees of relatedness and from there outlines the cell lineage tree. To check their system, they pitted it against the tried and true method of observing cell divisions as they occurred in a lab-grown cell culture. The team found that, from an analysis of just 50 microsatellites, they could successfully recreate an accurate cell lineage tree.
     
While the research team plans to continue to test their system on more complex organisms such as mice, several scientists have already expressed interest in integrating the method into ongoing research in their fields. Says Shapiro, who heads the project: 'Our discovery may point the way to a future 'Human Cell Lineage Project' that would aim to resolve fundamental open questions in biology and medicine by reconstructing ever larger portions of the human cell lineage tree.'
 
Prof. Ehud Shapiro's research is supported by the M.D. Moross Institute for Cancer Research, the Dolfi and Lola Ebner Center for Biomedical Research, the Samuel R. Dweck Foundation, the Benjamin and Seema Pulier Charitable Foundation, the Robert Rees Fund for Applied Research, Dr. Mordecai Roshwald and the Estate of Klara (Haya) Seidman.  Prof. Shapiro is the incumbent of the Harry Weinrebe Professorial Chair
 
For additional information see www.weizmann.ac.il/udi/plos2005
 
Math & Computer Science
English

Pages