Bhubaneswar Mishra - US grants

The research is largely motivated by complexity considerations. To understand complexity of algorithms, it is often necessary to obtain good lower and upper bounds to commutative algebra. In the last few years, new bounds have been achieved in three key areas: namely, Groebner Bases, Hilbert Nullstellensatz and Wu-Ritt Characteristic Sets. The proof techniques employed are novel and contain ideas that have much wider potential applications. These and a few other related techniques will be further investigated and new algorithms based on these ideas will be devised. Another area is the construction of efficient algorithms -- for GCD. Sturm sequences, computations with algebraic numbers. Groebner bases and Wu-Ritt characteristic sets. Here also some important progress has been achieved. Further applications of these results to obtain decomposition of ideals and varieties, and extensions to more general classes of algebraic structures will be pursued. An important area that has not received much attention is the one dealing with the choice of data structures in algebraic algorithms . This seems a very exciting area because the computational objects (multivariate polynomials, ideals) here are much richer in structure than anything that has been traditionally studied in data structures. Research will be undertaken in this area to address issues of the following kind: Selection of data structures for various computational algebraic algorithms, Application of amortization and hashing techniques to algebraic data structures, etc.

This project seeks to create a disseminable, multi-functional, inexpensive and well-documented laboratory course sequence, with the primary goal of improving practical skills of undergraduate students specializing in robotics, vision, AI and manufactoring disciplines. The project will include the building of a robot, as well as supporting simulation and real-time software and hardware, and it will develop comprehensive laboratory manuals to support an undergraduate sequence of courses in robotics, AI and vision. The laboratory will be transportable.

This grant will support theoretical research into the geometric and control problems of grasping non-rigid and compliant objects. Related control problems will also be studied, such as task planning, non-holonomic motion planning, representation of compliance uncertainty, and decomposition of tasks into homogeneous subtasks such as grasping, re-grasping, and finger gaiting. The research is likely to integrate combinatorial task-planning algorithms with motion planning based on differentiable manifold theory. Experimental verification of promising algorithms is also planned.

This equipment award, for robotics and vision equipment, supports research in rapid prototyping, visualization, automated manufacturing, and dexterous manipulation. The visualization work aims to create an electronic environment for the building of objects to be manufactured. Rapid prototyping occurs when the electronic version of the object is translated into codes and fixturing sequences that enable the object to be manufactured. When this process is fully automated and optimized, then the goal of automated manufacturing has been met. The work on dexterous manipulation is tied into the manufacturing process because the factory of the future will need complex robots that are able to pick up and handle a variety of objects. This research project is one of the few projects in the United States that addresses the full range of issues that need to be addressed in automated manufacturing. The equipment will support basic research on vision (robots need to see), manipulation (robots need to grasp objects), machine tooling and planning from electronic media (allowing the rapid development of products), and factory task optimization (allowing the inexpensive, high quality, mass production of products).

9421935 Kedem This award is to purchase a small network of workstations with accessories and software to support 4 research projects: 1) Further development of Calypso, a software-based execution platform for high-performance computing. This experimental project grew out of previous theoretical work dealing with abstract machines. The current prototype will be further enhanced and tested on selected applications. Special attention will be paid to scalability, load balancing, and fault tolerance. 2) Experimentation with Persistent Linda, an implementation of a fault-tolerant Linda built on top of lightweight transactions. Large-scale experimentation will be conducted using multiple machines executing long-running parallel computations. 3) Construction of an experimental platform for the easy implementation and evaluation of fundamental, symbolic computation algorithms. Special attention will be given to making the platform robust, flexible, and portable. 4) Distributed extension to a novel, centralized persistent object system will be developed. The system will be enhanced by new facilities such as type security, distributed locking, distributed synchronization, and collaborative applications. ***

The primary goal of this research is to construct a theoretical framework for understanding and design of reactive devices starting from the description of a high-level task. The research is based on a new class of robot algorithms that the PI calls ``reactive algorithms.'' These offer insights into how a robot itself can use its body parts like "analog computers'' and be computationally more powerful than its "digital brain,'' and perhaps may ultimately shed some light on the question of how insects with far fewer neurons than a robot are able to accomplish much more complicated manipulation and locomotion tasks. So far the main applications of these ideas have been in constructing new parallel-jaw grippers and multifingered (2- and 3-fingered) hands, a "twirling-machine'' and a walking machine. The PI has built a prototype parallel-jaw gripper ("NYU reactive gripper'') based on these algorithmic ideas. The resulting gripper reduces the necessary computing power to only a few simple digital circuits, utilizes primitive sensing abilities, i.e., no more than a dozen infra-red emitters and detectors and operates in a smooth manner without disturbing or damaging the manipulated objects. The PI has been investigating how to describe these devices and prove their correctness using the Ramadge-Wonham Discrete Event System (DES) formalisms. Another goal is to understand the "computational'' complexity of these devices based on a framework for analyzing the "competitiveness'' of on- line algorithms in comparison to an idealized clairvoyant algorithm. Other theoretical questions relate to the effect of noise, algorithmic modification for immunization against noise, the sensor-placement problem, and stability and convergence properties.

EIA-0231601
Bhubaneswar Mishra
New York University

Designer Molecules for Biosensor Application

A two-day workshop to explore the feasibility of the state-of-the-art and potential short-term and long-term technology that can be used to quickly detect pathogenic microorganisms is being held at the Cold Spring Harbor Laboratory. In particular, merits of various technologies, based on genomic-expression (mRNA), genome structure (DNA/RNA), protein structure an other physical and geometric properties are compared. The multi-disciplinary collaborations of computer scientists, biologist, engineering, and biochemist is expected to in order to facilitate and advance in science of protein arrays for understanding cellular processes, detectors for monitoring single cells, and monitoring of pathogenic agents.

EIA-218568
Bhubaneswar Mishra
New York University

Mathematical and Algorithmic Analysis of Natural and Artificial DNA Sequences

The PI is developing tools that play an important role in understanding the properties of both natural and artificial genomes and thus, elucidates how such DNA evolves under natural and artificial conditions (in vitro or in vivo). The ultimate applications range from building error-resilient biological computers all the way up to understanding how genome structures (e.g., genes, gene families, synteny groups, haplotype blocks, chromosomes, etc.) have naturally evolved.

With this goal in mind, the PI is developing several modeling and statistical algorithms with efficient implementations in order to solve design problems in genomics, biosensors, biocomputation and evolutionary biology. The final "tool box'' design contains: a software environment and language that allows users to visualize and analyze long DNA or RNA molecules, a "gene grammar" to model various genome-wide evolutionary processes, statistical analysis of the structures of various natural genomic DNAs evolving under replication and proof-reading processes and finally, a physical annotation of the genome that can be used in designing genomic microarrays or aptamers for biosensors.

Many achievements in the biological and biomedical sciences are fueled by advances in technology and computational science. To address the complex challenges in the biological sciences in the 21st century, there is a growing need for professionals who can translate scientific problems in biology into mathematics and computations; for such productive work, familiarity with modern scientific computing approaches as well as key biological challenges is essential.

Intellectual Merit: This IGERT award is for a multidisciplinary Computational Biology (COB) doctoral program at NYU and MSSM targeting students interested in pursuing research in biology/biomedicine who require a transition from/to the mathematical/computer/physical sciences to best meet scientific challenges and career goals. This experimental, bidirectional program will offer integrative training that exploits NYU's strengths in applied mathematics, computer science, biology, and biochemistry, and Sinai's leadership in biomedicine. The major COB research themes - macromolecular modeling, computational genomics, and physiological modeling - will train students to investigate biological systems spanning wide temporal and spatial scales, from atoms and macromolecules, to cells and organs, to organisms. Modeling biological systems across such scales is essential for a modern systems biology approach aimed at understanding physiological processes and diseases and applying this knowledge to biomedicine.

To integrate training in biological and computational areas and provide trainees broad scientific perspectives and work experiences, the COB PhD program includes: (1) Dual faculty mentorship for thesis research; (2) Interdisciplinary training through flexible and background-tailored tracks in scientific computing and computational biology (courses in computer science, applied mathematics, biology, and biomedicine), trainee-led seminars, and ethics/research conduct courses, while ensuring competitive time to degree (5 years); (3) Summer internships in industry, academia, government (Agilent, IBM, Celera, Merck, Novasite and 3D Pharmaceuticals, supercomputing centers), or international laboratories; (4) Learning environments and activities that promote interdisciplinary interactions and broader collaborations within and outside NYU/MSSM, including: trainee-led COB seminars, annual COB retreat, and common COB lab/lounge; and (5) Mentoring and career development activities to ensure student retention, especially women and underrepresented groups, through student advisory committees, trainee-led support group, and partnerships with Burroughs Wellcome Fund and NYC's IGERT programs at CUNY and Columbia. The COB doctoral program will be evaluated and evolved continuously by its executive and internal/external advisors in close collaboration with the pedagogical experts of NYU's Center for Teaching Excellence (CTE).

Broader Impacts: COB will train math/computer science students to successfully model biological systems and, in turn, provide biology students the grounding in computational techniques so they can tailor the model and algorithms to specific biological problems. To help bridge disciplinary gaps, we will design background-tailored short (non-credit) courses before Year 1 and promote peer learning by pairing students from complementary backgrounds. We expect that COB's activities will enable trainees to act as catalysts for novel interdisciplinary collaborations and to acquire expertise in cutting-edge research areas; these experiences will prepare them uniquely for research and education careers in academia, industry, and government. In addition, COB's program of integrating scientific grounding, experience in team-oriented multidisciplinary projects, mentoring, and career broadening activities will serve as a new model of graduate training at NYU/MSSM and beyond, promote the development of curricula for computational biology, and provide the opportunity to develop the COB doctoral degree at NYU based on the new model. Recognizing the urgent need for diversity in the sciences, we will make concerted efforts in conjunction with participating departments and with successful new minority initiatives at NYU to recruit and retain the brightest students, especially women and other underrepresented groups.

IGERT is an NSF-wide program intended to meet the challenges of educating U.S. Ph.D. scientists and engineers with the interdisciplinary background, deep knowledge in a chosen discipline, and the technical, professional, and personal skills needed for the career demands of the future. The program is intended to catalyze a cultural change in graduate education by establishing innovative new models for graduate education and training in a fertile environment for collaborative research that transcends traditional disciplinary boundaries. In this sixth year of the program, awards are being made to institutions for programs that collectively span the areas of science and engineering supported by NSF.

The biological sciences are advancing by posing increasingly complex and quantitative questions which require experiments that are increasingly complex procedures, and analysis of increasingly complex and large data sets. Information technology is pervasive throughout this process. Before beginning the laboratory work, computation is necessary for planning the experiment, and for later analysis of the results. In gene chip experiments for determining gene activity levels, planning issues include which biological hypotheses should be considered and what chemical conditions will yield the most informative results, followed by computation to reduce the collected data, which can be gigabytes of information, to forms that can be understood and exploited by biological scientists. In electron microscope experiments for determining the 3-D structure of viruses, planning issues include electron energy, defocus level, beam current, number of tilts, and tilt angles, followed by computation to reduce the measured data, which can be one hundred thousand or more images, to a biologically-plausible 3-D structure. Historically, insufficient attention has been devoted to the use of highly sophisticated information technology for quantitative planning and analysis of experiments, which jointly takes into account the behavior of the measurement apparatus, the goals of the experiment, the unavoidable uncertainty in the system, and the algorithmic complexity that a particular experimental design implies for the subsequent computational analysis of the experimental data. The research objective of this ITR project is to bring together a team of investigators from MIT, Purdue and NYU-Courant along with their industrial collaborators to apply principles from information, coding and systems theory, along with advanced computational methods for statistical inference and numerical optimization, to create a unified approach to planning and analysis of complex quantitative experiments in the biological sciences, such as the determination of gene expression using gene chips and the determination of 3-D viral structure from scattering and electron microscopy experiments. These biological problems will challenge the state of the art in information technology and an important characteristic of the project is the parallel development of new information technology and new biological applications. The human-resources objectives of this ITR project are to provide the opportunity for undergraduate students, graduate students, and postdoctoral associates to learn about and contribute to this exciting area at the interface between information technology and biological sciences. Because of the biological focus of the research it is anticipated that the proposed project will be an outstanding opportunity to recruit women and other underrepresented minorities into the Systems, Information and Computer Science endeavor.

We seek to initiate an exploratory research program aimed at creating design tools for designing, optimizing, simulating and testing biological circuits built out of basic machineries of biology; specifically, mechanisms composed of DNA, RNA and protein interactions. These circuits are dispersed, asynchronous but are easily replicable as their basic components are created out of those elements that already occur in nature and can be synthesized, controlled and degraded using the same principles. The basic biological principles that they utilize are: polymerase-induced replication, transcription controlled by transcription activation, translation into proteins, interference by small RNA, and modulation via extra-chromosomal plasmids. Because of the underlying design principles, biological circuits created in this manner can be easily transfected into simple prokaryotic organism such as E. coli, eukaryotic organisms such as yeast as well as cell lines. We hope to gain a better understanding of the biological mechanisms of interest by studying the interaction between the designed biological circuit, whose operation is known, modeled and already studied, and the unknown function of the genes of the host organism. In this manner, the proposed research program extends the current functional genomics methods based on knock-in mutants, knock-out mutants, genes perturbed by extra-chromosomal plasmids and interference through RNAi.

Thus ultimately the proposed research is aimed at understanding gene networks through computational and mathematical methods using both forward engineering and reverse engineering paradigms. For forward engineering, we directly address various topics dealing with genetic circuits - in particular, we focus on creating novel artificial circuits out of regulatory genes, RNAs, and proteins. For the reverse engineering, in the context of our other related research, we have also addressed the problem of inferring gene networks with techniques analyzing time-course data in abundance data, such as transcriptome data, but not excluding proteome, or metabolome data. Furthermore, it should be apparent that in the near future these methods could play an important role in gene therapy, genetic modification of organisms or even large-scale systems to solve challenging computational problems.

The major computational challenge is the development of novel design principles for delay-independent asynchronous circuits using simple building blocks such as combinatorial logic-gates (AND, NOT, XOR, etc.), arbiter circuits (Muller C-circuit) and memory elements (FIFO queue elements).

Akin to a complex engineered system, biological processes operate through many simultaneous interactions within complex networks. Traditionally, biologists have constructed "models" to capture this complexity and verify their intuitions as well as communicate how a particular biological system or subsystem actually works. To build these models, biologists rely on a very general and broad array of knowledge, and also augment it with depth and expertise obtained from small number of exemplar systems. With availability of large amount of high-throughput experimental data, biologists are also faced with the task of reconstructing models from data where relevant information may be deeply buried in layers of numerical information.
Biological models are often presented pictorially as graphs and flow charts with many components, each corresponding to a certain biochemical reaction. Such diagrams have also, but not always, been associated with mathematical models, mostly in the form of differential equations. The equations are used to perform simulations of the system, when they have a well-defined set of kinetic parameters. The model is refuted or validated depending on whether the simulated traces agree with biological data.

Often one is faced with situations, where there is no mathematical model, or the model is incomplete and they lack a complete set of parameters, and yet biologists do have detailed descriptive understanding of many of the components and their interactions. For instance, current microarray data analysis techniques draw the biologist's attention to targeted sets of genes but do not otherwise present global and dynamic perspectives (e.g., invariants) inferred collectively over a dataset. When ontologically invariants are inferred from experiments (using GOALIE redescription tool), such invariants can be compared with the known descriptive information to determine if we have complete and consistent theories about certain biological processes.
This project addresses these two scenarios by providing automated reasoning tools that bridge both computational and descriptive models in biology. The results from these tools and experimental analyses hint at the construction of efficiently testable predictions. The results of wet-lab experiments are then used to refine and amend the formal model. This feedback cycle between modeling and experimentation has proven important in obtaining a process-level understanding of the underlying cellular machinery.

The further characterization of specific parts of the mammalian cell cycle behavior (e.g. how a possibly unknown factor may allow the phosphorlyzation Cdk inhibitor p27 by Cdk2 at G1/S.)
In the longer run, understanding the wider implications of the complex regulatory and metabolic architecture of the cell cycle will provide significant insights into new applications of biology and advanced computing. In addition, they will provide new perspectives on computing by exploiting biologically driven metaphors. More importantly, the approaches developed in the context of hybrid-system (HS) models and bio-ontology will find applications to swarm robotics, social-software, e-commerce, complex interactive engineered systems, computer-security, adaptive software, etc., although from our own historical perspective, we will remain engaged in proving the first successes of this approach in biomedical applications.

[unreadable] DESCRIPTION (provided by applicant): We seek funding to develop, within 10 years, a technology to sequence a human size genome of about 6 Gigabases including both haplotypes. We aim to accomplish these goals by successfully integrating three different component technologies: (1) Optical Mapping to create Ordered Restriction Maps with respect to an enzyme, (2) Hybridization of a pool of oiigonucleotide probes (LNA probes) with Single Genomic DNAs on surface, and (3) Algorithms to solve "localized versions" of PSBH (Positional Sequencing by Hybridization) problems over the whole genome. The project is planned in two stages: (1) Pilot Study to Assess Scientific Soundness [R21] and (2) Large-Scale System Engineering [R33]. The R21 phase aims to demonstrate first the soundness of whole-genome mapping of LNA probe hybridization sites, and then algorithmic feasibility of combining these maps into haplotype sequences. The potential for success of these two aims may be inferred from our preliminary work on (1) haplotype mapping of T. pseudonana and a segment of human chromosome 4; (2) fluorescent imaging of DNA and its validation by AFM technology; and (3) existing body of work on optical mapping by our investigators. The R33 phase aims to engineer the final system by constructing in succession: (1) high throughput optical system, (2) preliminary validation by sequencing 100bp segment of P. falciparum genome (small-size), (3) more complex validation by sequencing 100bp segment of H. sapiens genome (large-size), (4) final system engineering and validation by sequencing the entire H. sapiens genome. [unreadable] [unreadable]

Collaborative Research:
0836656 (Peter Doerschuk, Cornell University)
0836649 (Bud Mishra, NYU)
0836720 (Sanjoy Mitter and Emery Brown, MIT)
Title: Discovery of Succinct Dynamical Relationships in Large-Scale Biological Data Sets


ABSTRACT:

Many types of information in neuroscience and molecular biology can be described as a set of measurements taken repeatedly as some index changes its value. In some situations, such as transcriptomic data measuring gene activities, the index is time while in other situations, such as in genetics association study, the index is position in a genomic DNA sequence and, in any case, the complete collection of data is referred to as a time series. Inference is the process of taking such time series, probably corrupted by errors, and computing answers to the following sorts of questions: (1) What is the system that generated the time series? For instance, if the system is known to be a differential equation of a specific type, what are the parameter values in the differential equation? (2) Given a completely specified system and a time series, did that system generate that time series? For instance, if a biologist has hypothesized a system that describes gene expression for a particular set of genes and then measures expression data, is the data compatible with the system, or equivalently, the hypothesis? (3) Given two time series, were they generated by the same system? For instance, if the pattern of nerve firings in a neural system is recorded in two different experimental situations, is the pattern the same or is it different? The four Principal Investigators are focused on three different biological application domains at three different biological scales: (1) the phenotyping of animal and human ethanol-consumption behavior (whole organism scale), (2) the pattern of action potentials measured on ensembles of neurons (cell-population scale), and (3) the time course of gene expressions as governed by the regulatory circuits of the cell (cellular scale). The types of challenges that are encountered in these applications include the following characteristics: the information is distributed over long periods of time rather than concentrated in time; the systems include delays and feedback paths; and the systems are highly nonlinear, including switching behavior, rather than linear. The major methodologies that will be developed and combined to solve inference problems in these application areas are: (a) information theory and stochastic control, (b) multi-scale approaches to learning the geometry of the data, and (c) computer algebra and symbolic computation. For example, to deal with the presence of delay and feedback in neuroscience systems, especially in the context of the interaction between information and stochastic control, requires a fundamental rethinking of classical information theory as it is employed in technology-based communication systems.

As the cost of computing decreases, computing becomes increasingly pervasive. A major purpose of pervasive computing is the real-time collection of high-dimensional time series of very diverse types of data including biological, medical, financial, communication systems status, power systems status, etc. The project will provide computational algorithms and software to analyze this data in more sophisticated ways and thereby extract more sophisticated information. Action taken upon this more sophisticated information, e.g., personalized medicine based on individualized genomic information or more accurate and flexible control of power systems thereby avoiding blackouts, will have important human and economic benefits to society. An important component of the project is educational, e.g., three graduate students working on the project will receive tuition and stipend and an unrestricted number of undergraduates will participate through a variety of ways, e.g., project courses. By attracting talented students to science and technology and providing challenging research experiences, the project will have important work force benefits to society.

"This award is funded under the American Recovery and Reinvestment Act of 2009
(Public Law 111-5)."

Summary: Formal Analysis of Complex Systems

A Collaborative Proposal Involving CMU, CUNY, NYU, Stony Brook, UMD, Cornell, JPL


This Expedition, under the directorship of Lead PI Edmund M. Clarke, will develop new computational tools to help scientists and engineers analyze and understand the behavior of the complex models they develop for application domains ranging from systems biology to embedded control. Building on the success of model checking and abstract interpretation (MCAI), two well-established methods for automatically verifying properties of digital circuit designs and embedded software, this research project will extend the MCAI paradigm to systems with complex continuous dynamics and probabilistic behaviors. Challenge problems providing technology drivers and testbeds for the research include: understanding the precursors and course of pancreatic cancer; predicting the onset of atrial fibrillation; and obtaining deep design-time insights into the behavior of automotive and aerospace control systems. Ultimately, this Expedition is expected to provide vital tools that will enable health-care researchers to discover better treatments for disease and will allow engineers to build safer aircraft and other complex systems.

The world-class team of scientists and engineers assembled for this Expedition includes two Turing Award winners, a recipient of the National Medal of Science, and awardees of other prestigious research prizes. Outreach consists of the development of a new, highly ambitious and highly cross-discipline educational program called Complex Systems Science Engineering, an annual Minority-Focused Intersession Workshop for Undergraduates on Understanding and Analyzing Complex Embedded and Biological Systems to be hosted at member institution Lehman College, CUNY; substantial financial support for undergraduate research; student involvement in the NASA JPL Research Affiliates Program; and other research opportunities for undergraduate and graduate students and postdoctoral trainees.

More information: http://www.mcai2.org/