Manolis Kellis
Research Interests

Distinguished Alumnus (1964) Career Development Professorship.
Associate Professor, MIT Department of Electrial Engineering and Computer Science (EECS).
Principal Investigator, Computer Science and Artificial Intelligence Laboratory (CSAIL).
Associate Member, Broad Institute of MIT and Harvard (Broad).

My primary research interests are in Computational Biology. My group is developing new algorithms and machine learning techniques for the interpretation of complete genomes, the understanding of gene regulation, and the elucidation of evolutionary mechanisms and embryo development. I am additionally involved in various research projects in Machine Learning, Computational Geometry, Robotics, and Information Retrieval.

I did my Ph.D. thesis on computational genomics, with Eric Lander and Bonnie Berger.
I did my masters thesis on image interpretation and retrieval, with Patrick Winston.

I also developed new computational methods to address the greater challenge of de novo regulatory motif discovery. Regulatory motifs are short 6-8 nucleotide sequence tags recognized by specific proteins that control gene expression, dictating when the associated genes will be turned on or off. Regulatory motif discovery has typically relied on extensive experimentation, evaluating gene expression of thousands of genes across dozens of experimental conditions, then constructing clusters of genes that show similar patterns of expression and searching their upstream sequences for over-represented sequence tags. In absence of biological knowledge of functionally related sets of genes, the identification or regulatory motifs has remained an open problem. Previous comparative studies have focused on individual instances of regulatory motifs, searching for conservation islands in intergenic regions. Such methods lack the power to discover the true motifs within these islands, since additional bases surrounding the motifs are spuriously conserved, not by natural selection but due to lack of divergence time between the species compared.

I approached regulatory motif discovery using genome-wide methods, evaluating motif conservation simultaneously across the entire genome. I found that the spuriously conserved bases surrounding a motif varied across its different instances, allowing the signal of the true motifs to stand out. Computationally, the algorithm started with an exhaustive enumeration of short sequence seeds with non-random genome-wide conservation, followed by a motif refinement and collapsing step, leading to a small dictionary of discovered motifs. These included nearly all previously known regulatory motifs, and a similar number of novel motifs, most of which showed functional specificities. Overall, the purely computational method showed unprecedented power in extracting signal from noise. The discovery of such genome-wide signals would have been impossible using traditional gene-by-gene experimental approaches, regardless of the time and effort invested.

I have additionally applied computational methods to understand mechanisms of evolutionary innovation. It is generally thought that new functions arise by duplication of existing genes, but the mechanisms of duplication have been poorly understood. For example, the ancestry of hundreds of duplicated human and yeast genes has been under debate, some scientist arguing for complete genome duplication and others for independent duplication events. Previous comparative work has focused on divergence of individual gene families or regions, and the analyses have remained inconclusive.

I have taken a genome-wide approach to address this question in yeast. Instead of using divergence rates of individual genes, I have focused on the conservation of gene order across the entire genome. My approach relied on a key dataset: the sequence of yeast species that diverged prior to the estimated time of duplication. My genome alignment methods provided definitive proof of complete genome duplication: every region of the newly sequenced relative corresponded to exactly two regions of the yeast genome. More than 90% of duplicated genes were lost in one copy or the other, but the remaining genes provided a sufficient signal to show complete duplication. This work has put an end to a long debate on the ancestry of the yeast genome that started nearly seven years ago with the completion of its sequencing. Additionally, the analysis led to the first genome-wide study of the emergence of new gene functions after duplication, with important revelations on the emergence of anti-viral defense mechanisms, environmental stress response, gene silencing and transcriptional regulation.

Hox genes control the anterior-posterior axis of embryo formation during development. By comparing the intergenic regions of human, baboon, mouse, and rat hox clusters, we are trying to understand the reasons behind the preservation of sequence and spacing.

My masters thesis was on Computer Vision, more precisely, sketch-based image retrieval. The project involved image understanding, segmentation, representation and learning (more about Imagina)

Developped a new represenation for full-body 3D motion data. The goal is to find lower-dimensional manifolds that contain motion patterns for different activities, embedded in a 27-dimensional space defined by the angles of joints. Finding such structure in human motion would allow to describe activities much more compactly for recognition or generation of 3D motion in terms of primitives intrinsic to the dynamics of human anatomy.

Presented a compact angle representation for handwritten characters based on online data that filters noise and facilitates recognition. Wavelet decopmosition of the character signal in derivative angle space is invariant to scaling or rotation and remains preserved within samples of the same character. Code in Matlab. Supervised by Paul Viola from the Learning and Vision group of the AI Lab at MIT.

Under the supervision of Patrick Winston, more interested in understanding the human I/O channels, I wrote a program to recognize music by learning patterns of attentional state. Instead of observing the notes directly, we were more interested in watching the states that a note observer would go through. In other words, the succession of primitive routines that a note pattern-matcher uses in observing a note sequence should tell us more about a musical piece than the patterns extracted themselves. The strength of this project was a clean architecture for using meta-information about an observed phenomenon. It separated the low-level primitive routines (that match patterns, change the focus of attention to salient points, and establish properties about the observed events) from an attentional state observer of those low-level routines (that records and analyzes series of states the pattern matcher enters). This separation that the program exhibited is suggested by Minsky's notion of a B-brain that monitors the activity of our A-brain. (visit the MOOD team)

My involvement in graphics also grew out of mathematical interest, in computational geometry. At Xerox PARC, I worked with Marshall Bern and Nina Amenta on a surface reconstruction algorithm. The algorithm relies on Voronoi diagrams and Delaunay triangulations to compute a provably correct reconstruction of the connectivity of a set of scattered sample points in space. Furthermore, the sampling density requirement is proportional to the curvature and proximity of other surface patches, which allows less dense sampling in those parts of the figure with fewer features. Our implementation reached speed and correctness benchmarks that were state of the art, and our work was published the subsequent summer at ACM Siggraph 1998, the largest graphics conference. (learn more about the Crust algorithm). Computer graphics was my new passion.

Back at MIT I took a computer graphics class and as a final project I proposed and implemented a 3D morphing algorithm. The project explored the question of transforming a three-dimensional polygonal model into another while minimizing the energy lost in creating and destroying polygons and maximizing the uniformity of the polygon flow. Following these constraints, a polygon can spawn another polygon from one of its edges (birth), and a polygon can collapse onto another polygon's edge (death). From there followed two algorithms I called Edge Ordering and Incremental Edge Ordering that solve the general problem of scheduling a multitude of agents to satisfy a set of tasks, for example a set of robots extinguishing small fires. Further constraints were applied on the birth and death edges to preserve the uniformity of the polygon flow, and the aesthetic results were very appealing, yet biased by the cost metric I used. (you can find 3D morphing examples online)

I made this system a reality in my 6.115 final project, RoboLogo, in a team of three people. Inspired from Seymour Papert's work with children and Logo, we developed iLogo (interactive Logo), to extend the Logo language with primitives for interacting with the environment, reading sensors, and reacting accordingly to external events. We designed the new language and its grammar; we built a compiler that translated programs from iLogo to assembly code; we wrote a library of low-level routines and initialization code to be linked with the generated files; we designed and laid out a printed circuit board to incorporate a processor, RAM, ROM, motor controllers, sensor drivers, AD converter; finally we put everything together on a mechanical truck on which we mounted sensors and actuators. Children can control the robot by writing simple high level commands in iLogo, and see a working robot bounce between two walls with only six lines of code. This new abstraction layer allows for more complicated behaviors to be expressed in smaller, simpler programs, with an overhead that is negligible when the speed of the processor is compared to the speed of external events. Building the entire RoboLogo environment from the ground was a very rewarding experience and went a step further than 6.270 where the circuit board was provided along with the iC language and compiler. Making RoboLogo happen was like constructing our own 6.270 class. (on to the RoboLogo page).

At Xerox PARC, the summer of 98, I worked on a larger-scale robotics project and I concentrated on the control of the robots rather than the low-level construction of the hardware. I worked with Mark Yim on Polypod, a unit-modular reconfigurable robot, and I was responsible of the control architecture for coordinating the actions of the different modules. The model I proposed is a combination between a global bus carrying one or multiple values shared among all modules and a message passing mechanism that provides an interpretation for the shared values. The architecture is designed to be adaptive to the environment and robust against isolated module failures. To decentralize the control it distributes the computational power throughout the robot and specifies local behavioral rules at the module level, so that global communication be not necessary for simple decisions that need only local information. Global behavior then emerges at the robot level when Polypod interacts with the environment. While working on Polypod, my graphics background helped in the making of a Java3D simulation to visualize the modules; my geometry background helped me work out the forward and inverse kinematics; my background in AI helped me develop an architecture for decision making and control arbitration; my mathematical background helped me address scalability issues and design algorithms for information propagation and storing; moreover, having dealt with both mechanical and electronics issues during my robotics experience at MIT, I had an intuition about what was feasible to undertake in a mechatronics system. (see more at the PolyPod page)

My interest in artificial intelligence arose as a mathematical curiosity first. In an introductory AI class, I was presented with a series of small independent problems and smart ideas with which to approach them. I applied those ideas in different projects in an intensive class by Tomás Lozano Perez, for which I trained a Neural Network to recognize human faces, I used Temporal Difference Learning for a board game in which the machine grew sometimes stronger than the user, and for my final project, I experimented with different machine learning methods to extract patterns from the stock market. (more about Invest)

My interest in building and controlling robots was first expressed when I participated in 6.270, the autonomous robot design competition. My brother was a junior in course VI, my sister a sophomore in course II and I was a freshman at the time. Together, we constructed a robot out of Lego pieces, and we programmed it in iC (interactive C) using a provided circuit board. The goal was to create insect-like robots, or more specially, ants. The "ants" were supposed to collect as much "food" as possible during each 60-second face-off. The food was represented by styrofoam blocks. Robots received more points for picking up the blocks and stacking them on top of each other in its "nest," a raised rubber platform. This experience taught me a lot about the difference between programming and reality, and how many things one needed to take care of when programming a system that interacts with the real world, even in an overconstrained environment like the contest table. (visit the RoboAnt contest page). I was thinking that children in high school, and even primary school should have the same opportunity to program autonomous robots. However the overhead from mechanical, electronics and low-level aspects should be reduced for younger children. They should start in a system with instant gratification, where they can write their "Hello, World!" program in a high level language on the first day. Writing complex programs, more complete reactions to the environment, and understanding the tools that make their program really work should be part of further lessons. They should however, immediately see the robot act and react around the lab under their commands and bridge the gap between concrete world actions and abstract programming commands.

The picture on the right was generated by a ray tracer that I wrote using C and OpenGL (see example 1 or 2). Other parts of the graphics pipeline I implemented were color interpolation, normal interpolation for Gourauld shading, casting shadows, and handling transparency. Other graphics work I did included a 3D model of the MIT campus (with some artistic liberties taken), including animations of a rowing race and traffic cars. Here's a contact-inspired graphic. The rings were animated.