• Research Assistant, Department of Computer Science, Duke University (May 2003 - Dec 2007)

Fault tolerance in algorithmic self-assembly; Design of new and powerful self-assembly models; Stochastic Modeling of DNA based nanorobotical devices; Algorithmic, graph-theoretic, and complexity-theoretical problems in self-assembly; Stochastic analysis of reversible self-assembly; Design and experimental implementation of DNA nanorobotical devices; Experimental implementation of DNA based self-assembly.

• Research Intern, Max Planck Institute, Saarbrucken, Germany  (May 2001-July 2001)

Project: Linear Time Algorithm for Single Source Shortest Path

Supervisor : Mr. Ulrich Meyer (MPI ,Germany) 
The project involved implementing a  SSSP ( single source shortest path ) algorithm for arbitrary directed  graphs  with random edge weights uniformly distributed in (0,1] and the algorithm needed O(n+m) time with high probability. It was basically based upon adaptive bucket spliting and label-correcting approach.  

Publications List [ DBLP Entry ] [Citeseer Entry]:

• John H. Reif, Sudheer Sahu, Peng Yin,  Compact Error-Resilient Computational DNA Tiling Assemblies, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004. Lecture Notes in Computer Science, Springer-Verlag, New York, (2004). 
  
  This paper describes the designs for compact methods of fault-tolerance in algorithmic self-assembly known as compact error resilient schemes. The scheme, based on 2-way   overlay redundant computations,  reduces the error probability from $\epsilon$ to $\epsilon^2$ for algorithmic assemblies having at least one Boolean function as  XOR. The error probability is further improved  to $\epsilon^3$ using 3-way redundant computations for a restricted class of Boolean functions.
  
• Peng Yin, Andrew J. Turberfield, Sudheer Sahu, John H. Reif,  Design of an Autonomous DNA Nanomechanical Device Capable of Universal Computation and Universal Translational Motion, Tenth International Meeting on DNA Based Computers (DNA10), Milano, Italy, June 7-10, 2004. Lecture Notes in Computer Science, Springer-Verlag, New York, (2004).

This paper presents a design of a nanomechanical DNA device that autonomously mimics the operation of a 2-state 5-color universal Turing machine . The states and transition-rules of turing machine are encoded in the various DNA sequences used in the design.  

• John H. Reif, Thomas LaBean, Sudheer Sahu, Hao Yan, Peng Yin,  Design, Simulation, and Experimental Demonstration of Self-Assembled DNA Nanostructures and DNA Motors, Computational Modeling and Simulation of Materials (CIMTEC) Conference, Acireale, Sicily, Italy, May 29-June 4, 2004.  Lecture Notes in Computer Science, Springer-Verlag, New York, (2005).
  

We present an overview of the theoretical models, algorithms and our softwares for simulation and design of DNA tiling assemblies and DNA nano-mechanical devices. We also discuss our laboratory demonstrations of DNA lattices and motors, including those using the designs aided by our
software.

• John H. Reif, Sudheer Sahu, Peng Yin, The Complexity of Graph Self-Assembly in Accretive Systems and Self-Destructible Systems., Eleventh International Meeting on DNA Based Computers (DNA11), Ontario, Canada, June 6-9, 2005. 

Complexity theoretic analysis of Graph Assembly Problem (GAP) : NP-completeness of Accretive GAP, #P-completeness of stochastic AGAP and P-SPACE completeness of Self-destructible GAP.

• Peng Yin, Sudheer Sahu, John H. Reif, Autonomous DNA Cellular Automata. Eleventh International Meeting on DNA Based Computers (DNA11), Ontario, Canada, June 6-9, 2005. 
  In this paper, we describe the design of an Autonomous DNA Cellular Automaton (ADCA), which can perform parallel universal computation by mimicking a one-dimensional (1D) universal cellular automaton. The states and transition-rules are encoded in the various DNA sequences used in the design. The key technical innovation is ``reaction waves'': a  mechanism to synchronize and pipeline events that are otherwise independent. 

• Sudheer Sahu, Peng Yin, John H. Reif, A Self-Assembly Model of DNA Tiles with Time Dependent Glue Strength. Eleventh International Meeting on DNA Based Computers (DNA11), Ontario, Canada, June 6-9, 2005. 
  

We propose a theoretical self-assembly model known as Time Dependent Glue (TDG) model, in which the glue strength between two juxtaposed tiles is a function of the time they have been in neighboring positions. We model the processes of catalysis and self-replication under TDG, and study  the tile-complexity for assembling shapes in our model and show that a thin rectangle of size kXN can be assembled using O(log N/loglog N) types of tiles, for any constant k>0.

• Urmi Majumder, Sudheer Sahu, Thom LaBean, John H. Reif, Design and Simulation of Self-Repairing DNA Lattices. Twelfth International Meeting on DNA Based Computers (DNA12), Seoul, Korea, June 5-9, 2006.

The paper describes a special class of DNA tiling designs called reversible tiling designs which when carefully designed can provide inherent self-repairing capabilities to patterned DNA lattices so long crystal growth/regrowth happens with respect to at least two adjacent binding sites. We discuss the design, simulation and a preliminary DNA implementation of a particular instance of carefully designed reversible tiling which we callReversible XOR. We further note that although in theory one can transform any irreversible computational DNA tile set to its reversible  counterpart and hence improve the self-repairability of the computational lattice.

• Sudheer Sahu, Bei Wang, Peng Yin, John H. Reif, DNAModeller: Modeling DNA based Molecular Systems. Twelfth International Meeting on DNA Based Computers (DNA12), Seoul, Korea, June 5-9, 2006.
  
  In this paper, we present a framework for a discrete event simulator for simulating the DNA based nanorobotical systems. The conformational changes of long chain DNA molecules are modelled using metropolis algorithm. The molecular motion is modeled as a stochastic process (brownian motion), and collision detection methods are employed to detect molecular collisions. Various chemical reactions like  hybridization/dehybridization are modeled as markov chains and strand displacement is modelled as a biased random walk. 
   
• Sudheer Sahu, John Reif, Capabilities and Limits of Compact Error Resilience Methods for Algorithmic Self-Assembly in Two and Three Dimensions. Twelfth International Meeting on DNA Based Computers (DNA12), Seoul, Korea, June 5-9, 2006.
  
  This paper presents a comprehensive theory of compact methods of fault tolerance in algorithmic self-assembly: an extension to our previous work on compact error resilient algorithmic self-assemblies. We present a compact error resilient scheme that reduces error from $\epsilon$ to $\epsilon^2$ for algorithmic assemblies with any arbitrary Boolean functions. Also, we characterize a restricted class of input-sensitive Boolean functions only within which error reduction from $\epsilon$ to $\epsilon^3$ is possible using compact error resiliency, and proposed a scheme for the same. Further we prove that reduction of errors from  $\epsilon$ to $\epsilon^4$ is not possible for any algorithmic assembly using compact error resilient methods. In addition to this, similar fault tolerance theory for three dimensional algorithmic self-assemblies is developed.

• Peng Yin, Sudheer Sahu, Rizal Hariadi, Harry M.  T. Choi, Sung Ha Park, Bethany Walters, Thomas H. LaBean, John H. Reif,  On Constructing Tile-less DNA Ribbons and Tubes. Twelfth International Meeting on DNA Based Computers (DNA12), Seoul, Korea, June 5-9, 2006.
  This paper describes a new tile-less approach to construct DNA lattice structures, in which the intermediate construct of tiles is bypassed. Single stranded DNA is used to directly form the intended DNA lattice.  The tile-less approach,  intended to serve as a complementary approach to the current dominant paradigm of tile-based approach, can often offer the following desirable properties: conceptual and structural simplicity, finer-grained programmability/higher information density, and higher thermal stability. We describe a general scheme that has been proved successful for the construction of extended DNA ribbons with programmable width and the construction of long DNA tubes.

•  Urmi Majumder, Sudheer Sahu, and John H. Reif, ``Reversible   self-assembly of squares as a rapidly mixing markov chain'', Fourth    Conference on Foundations of nanoscience: self-assembled architectures    and devices (FNANO07), Snowbird, April 18-21, 2007.

This paper presents stochastic modeling of reversible self-assembly process that includes the determination of equilibrium concentrations and rate of convergence to equilibrium. We prove that an assembly in chemical equilibrium implies that the corresponding markov chain has reached its ergodic limit. Based on the convergence rate analysis for the self-assembly of linear systems and assembly of  $n\times n$ square, we conclude that the corresponding markov chains are rapidly mixing. In fact, the tile system continues to converge to equilibrium exponentially fast even when we allow errors in the system. We extend the analysis to general shapes in two-dimensions and three-dimensional assembly of a $n\times n\times n$ cube.

•  John H. Reif, Sudheer Sahu, ``Autonomous Programmable DNA  Nanorobotical Devices using DNAzymes'',  \emph{Fourth Conference on  Foundations of nanoscience: self-assembled architectures      and devices (FNANO07), Snowbird, April 18-21, 2007.}
  We designed a DNAzyme calculator, a finite state automata device (DNAzyme FSA) that  executes finite state transitions using DNAzymes, its extension to probabilistic and non-deterministic automata, their applications as DNAzyme router, and DNAzyme porter. In addition we present DNAzyme doctor that can provide transduction of nucleic acid expression: it can be programmed to respond to the under-expression or over-expression of various strands of RNA, with a response by release of an RNA. For the stochastic modeling of the these devices,  the activity of a DNAzyme is modelled as a reversible markov chain and the strand displacement process as a  biased random walk.
  

• John H. Reif, Sudheer Sahu, ``Optimal Algorithms for Oblivious Group Testing Problems''. In preparation.

We present a randomized algorithm for oblivious group testing that detect d=o(n) defective items from a set of n objects in O(dlog(n/d)) oblivious tests, where a test can determine the existence of any defective item in that test-sample. We prove the matching lower bound on number of tests, hence showing the optimality.  

•  Sudheer Sahu, John H. Reif, ``Approximate Pattern Matching for Entropy Bounded Text''. In preparation.

We present an algorithm that runs in $O(n\log m/pm)$ expected time where $H$ is the entropy of the text and $p=1-(1-H^2)^{\frac{H}{1+H}}$ based on preprocessing of the text.

•  Peng Yin, Bo Guo, Christina Belmore, Sudheer Sahu, Will Palmeri, Erik  Winfree, Thomas H. LaBean,  John H. Reif, ``TileSoft: Sequence  Optimization Software for Designing DNA Secondary Structures''. In Preparation.

A crucial computational problem in constructing DNA objects is the design of DNA sequences that can correctly assemble into desired DNA secondary structures. TileSoft described here deliver the following features: 1) Its graphical user interface renders the molecular architect the ability to define DNA secondary structure and accompanying designing constraints directly on the interface as well as the ability to view the optimized sequence information pictorially. 2) Its fully automatic optimization module relieves the user of the drudgery of manually dictating the sequence selection process, and its evolutionary algorithm produces satisfactory results efficiently. 3) Its graphical user interface and its optimization module are smoothly integrated from user's perspective, while they are at the same time well separated in terms of software architecture, making each amenable to future improvements without negatively affecting the other.

Technical Reports

• Clustering Error-Prone Gene Expression Data

Supervisor: Prof. Alexander Hartemink (Duke university)
Course  :  Computational Functional Genomics (Jan 2003-April 2003)
We worked on improving the algorithm given by Ben-Dor for clustering the gene expression data that is not error-free.  We had to look at the representational graph for the given data, and find out the connected components.

• Genome Rearrangement with Gene Families

Supervisor : Prof.  Alexander Hartemink ( Duke University)
Course  :  Algorithms in Computational Biology (Sep 2002-Dec 2002)
The problem was to design an algorithm for finding the exemplar breakpoint distance between two strings(genomes). We modified the Sankoff's algorithm, and found this new algorithm to perform much better than Sankoff's algorithm. It was like searching through a tree, and we improved the strategy for calculations done at nodes and the pruning method.

• Accurate Static Branch Prediction using Value Range Propagation

Supervisor: Prof.  Gershon Kedem ( Duke University)
Course :  Computer Architecture (Sep 2002-Dec 2002)
A new approach to static branch prediction known as Value Range Propagation(VRP) was implemented and compared to other approaches. The algorithm for VRP used concepts like control flow graph, ssa-edges, phi-functions, variable renaming, loop carried dependence.

• Cache-Efficient Fast Fourier Transform

Supervisor : Prof. Sandeep Sen (IIT Delhi)
Course : B.Tech Project (July 2001-May 2002)
A cache-efficient algorithm was designed and implemented for FFT calculation. The basic idea was to apply emulation theorem upon I/O model algorithm. It does FFT using butterfly on small subsets of input and then does matrix-transposition to reach onto the next stage of butterfly. It was found comparable to FFTW( fastest fourier transform in the west) in running time.

• Linear Time Algorithm for Single Source Shortest Path

Supervisor : Mr. Ulrich Meyer (MPI ,Germany)
Course      : Summer Internship (May 2001-July 2001)
The project involved implementing a  SSSP ( single source shortest path ) algorithm for arbitrary directed  graphs  with random edge weights uniformly distributed in (0,1] and the algorithm needed O(n+m) time with high probability. It was basically based upon adaptive bucket spliting and label-correcting approach.

• Terrain-Visualisation

Supervisor : Prof. Sanjeev Kapoor (IIT Delhi)
Course       : Mini-Project  (Jan 2001-May 2001)
A terrain is given and using delauneys triangulation techniques the silhouettes and maps were extracted. Horizon trees were implemented to store these maps and silhouettes. A variant of sweepline algorithm was used to clip the map edges and silhouette edges, fastly. We also proposed a solution to counter the break in monotonicity of monotone chains and showed the solution was correct for motion in any arbitrary direction.

• Hardware Sorter

Supervisor : Prof. M. Balakrishnan (IIT Delhi)
Course : Digital Hardware Design (Jan 2000 - May 2000)
Implemented bubble sort on FPGA board to sort 8-bit numbers, which were inputted to the RAM.

• Design and Simulation of processor based on PowerPC architecture with extended instruction set.

Supervisor : Prof. Anshul Kumar (IIT Delhi),
Course : Computer Architecture (July 1999-Dec 1999)
Processor based on PowerPC architecture was designed and simulated to support an extended instruction set. It was fully pipelined (stalling and forwarding included) and all the critical timing issues were observed.