System and method for determining a nucleotide sequence

Abstract

Described herein are systems and processes for designing the sequence of one or more interacting nucleic acid strands intended to adopt a target secondary structure at equilibrium. The target secondary structure is decomposed into a binary tree and candidate mutations are evaluated on leaf nodes of the tree. During a process of leaf optimization, defect-weighted mutation sampling is used to select each candidate mutation position with a probability proportional to its contribution to an ensemble defect of the leaf. Subsequences of the tree are then merged, moving up the tree until a final nucleotide sequence of interest is determined that has the target secondary structure at equilibrium.

What is claimed is: 
     
         1 . A method in an electronic system for determining a nucleotide sequence that can adopt a target secondary structure at equilibrium, comprising:
 decomposing a target secondary structure of a nucleic acid molecule into a binary tree structure having leaves and nodes, wherein the decomposition takes place at splice points within duplex stems of the target secondary structure;   designing a nucleotide sequence for each leaf within the binary tree;   recursing the binary tree to merge and reoptimize the nucleotide sequence for each node of the binary tree; and   determining the nucleotide sequence of the root node from the merged and reoptimized nucleotide sequences of the other nodes in the binary tree.   
     
     
         2 . The method of  claim 1 , wherein decomposing the target secondary structure comprises adding dummy nucleotides to the splice points of the decomposed target secondary structure. 
     
     
         3 . The method of  claim 2 , wherein recursing the tree comprising removing the dummy nucleotides when merging the leaves into parent nodes. 
     
     
         4 . The method of  claim 1 , wherein decomposing the target secondary structure comprising setting splice points at least a minimum number of base pairs from the end of the duplex stems. 
     
     
         5 . The method of  claim 1 , wherein designing the nucleotide sequence for each leaf comprises optimizing the nucleotide sequence of the leaf nodes of the tree to reduce an ensemble defect of each leaf node below a user-specified stop condition. 
     
     
         6 . The method of  claim 5 , wherein optimizing the nucleotide sequence comprises optimizing the ensemble defect using defect weighted mutation sampling so that a candidate mutation position in the nucleotide sequence is randomly selected with a probability proportional to the ensemble defect contribution of the nucleotide. 
     
     
         7 . The method of  claim 1 , wherein recursing the binary tree comprises identifying defective subtrees of the tree and re-optimizing any defective subtree by defect-weighted child sampling, wherein a child node is randomly selected for re-optimization with a probability that is proportional to the ensemble defect contribution of the child node. 
     
     
         8 . The method of  claim 1 , wherein designing the nucleotide sequence for each leaf within the binary tree comprises selecting an initial random nucleotide sequence to be compared against the decomposed target secondary structure at each leaf node in the tree. 
     
     
         9 . The method of  claim 8 , wherein the initial random nucleotide sequence is iteratively mutated to optimize the nucleotide sequence at each leaf of the tree. 
     
     
         10 . The method of  claim 1 , wherein the method is implemented in computer servers. 
     
     
         11 . The method of  claim 1 , wherein the target secondary structure comprises one or more nucleic acid chains. 
     
     
         12 . The method of  claim 1 , wherein the target secondary structure is converted into a matrix within a computer memory. 
     
     
         13 . The method of  claim 1 , wherein decomposing the target secondary structure further comprises identifying stem structures within the target secondary structure. 
     
     
         14 . The method of  claim 1 , wherein decomposing the target secondary structure further comprises decomposing the parental nodes until all the nodes are leaf nodes. 
     
     
         15 . The method of  claim 1 , wherein determining the nucleotide sequence of the root node further comprises providing a nucleotide sequence of a nucleic acid strand that adopts the target secondary structure. 
     
     
         16 . An electronic system for determining a nucleotide sequence that adopts a target secondary structure at equilibrium, comprising:
 means for decomposing a target secondary structure of a nucleic acid molecule into a binary tree having leaves and nodes, wherein the decomposition takes place at splice points within duplex stems of the target secondary structure;   means for designing a nucleotide sequence for each leaf within the binary tree;   means for recursing the tree to merge and reoptimize the nucleotide sequence for each node of the tree; and   means for determining the nucleotide sequence of the root node from the merged and reoptimized nucleotide sequences of the other nodes in the binary tree.   
     
     
         17 . A programmed storage device comprising instructions that when executed by a processor perform a method comprising:
 decomposing a target secondary structure of a nucleic acid molecule into a tree having leaves and nodes, wherein the decomposition takes place at splice points within duplex stems of the target secondary structure;   designing a nucleotide sequence for each leaf within the binary tree;   recursing the tree to merge and reoptimize the nucleotide sequence for each node of the tree; and   determining the nucleotide sequence of the root node from the merged and reoptimized nucleotide sequences of the other nodes in the tree.   
     
     
         18 . The programmed storage device of  claim 17 , wherein the programmed storage is a compact disk or DVD. 
     
     
         19 . The programmed storage device of  claim 17 , wherein designing the nucleotide sequence for each leaf comprises optimizing the nucleotide sequence of the leaf nodes of the tree to reduce an ensemble defect of each leaf node below a user-specified stop condition. 
     
     
         20 . The programmed storage device of  claim 17 , wherein recursing the tree comprises identifying defective subtrees of the tree and re-optimizing any defective subtree by defect-weighted child sampling, wherein a child node is randomly selected for re-optimization with a probability that is proportional to the ensemble defect contribution of the child node.