"
Team:USTC Software/Simulation
From 2010.igem.org
(→Chain Sorting and Weighting Scheme) |
(→Chain Sorting and Weighting Scheme) |
||
| Line 35: | Line 35: | ||
If all chains are different in the first stage of sorting, we have already obtain the unique order of the chain list. However, it is not always so: equal chains in the above sorting may be equivalent or not. It is due to the assumption that two bound parts are taken as equal. Though the above sorting strategy takes binding positions into consideration, it ignores the binding details of those parts: the details are hidden in the nodes of all trees. Hence, similar to the chain sorting, we need to find another strategy to sort nodes as well as trees. Our weighting scheme will be first introduced below. | If all chains are different in the first stage of sorting, we have already obtain the unique order of the chain list. However, it is not always so: equal chains in the above sorting may be equivalent or not. It is due to the assumption that two bound parts are taken as equal. Though the above sorting strategy takes binding positions into consideration, it ignores the binding details of those parts: the details are hidden in the nodes of all trees. Hence, similar to the chain sorting, we need to find another strategy to sort nodes as well as trees. Our weighting scheme will be first introduced below. | ||
| - | Assume the chains are sorted already. Each part will be assigned a weight based on its position in the chain list. The weight of the jth part on the ith chain is (i,j). For example, the first part on the first chain posses a weight (0,0) (in '''C''' style, counting number from zero). After assignment of parts' weight, we turn to weights of the nodes in trees. Since leaf nodes in trees are actually the representation of parts in | + | Assume the chains are sorted already. Each part will be assigned a weight based on its position in the chain list. The weight of the jth part on the ith chain is (i,j). For example, the first part on the first chain posses a weight (0,0) (in '''C''' style, counting number from zero). After assignment of parts' weight, we turn to weights of the nodes in trees. Since leaf nodes in trees are actually the representation of parts in bound state on chains, the weight of each leaf node could be inherited from the weight of its corresponding part. For parent node, its weight equals to the maximum of weights of all its children nodes (we define a weight (i, j) is greater than another (i',j') if i < i' or i = i' while j < j'). The recursive definition of nodes' weight of trees makes it possible to sort all children nodes of each node, which is a prerequisite for generating Huffman codes (see below). And then the tree order in the forest could be uniquely determined by sorting the root node of each tree. |
[[Image:USTCs_Chainsorting1.png|400px|thumb| Exchange of the first and second chain. The tree structures are different before and after exchange: the two chains are not equivalent.]] | [[Image:USTCs_Chainsorting1.png|400px|thumb| Exchange of the first and second chain. The tree structures are different before and after exchange: the two chains are not equivalent.]] | ||
| - | Back to the question above, if two chains | + | Back to the question above, if two chains are equal in the first stage sorting, which should be arranged in front of the other? The answer could be obtained by exchanging them. The exchange will change the parts' weight on both chains and thus the weight of some nodes of the trees. The tree structure is also possible to change. If the tree structure is not changed, the two chains are equivalent, which means that it makes no difference to arrange either chain in front of the other. If the tree structure changes, we must find some ways to determine which tree structure is preferred and based on this to arrange them. We know each tree could be uniquely converted to a binary tree by taking the first child of each node as the left child and its siblings as its right child. The Huffman algorithm is used to generate the Huffman code of each node in the binary tree. Since the Huffman code of each node represents its path to the root node, we can restore the tree structure from the Huffman codes of all leaf nodes. Hence, the Huffman codes of leaf nodes could uniquely determine a tree structure. We could generate a string, '''unicode_t''' for tree structure by splicing the Huffman codes and their weight of all leaf nodes sorted by their weights and adding a asterisk between two adjacent codes, for example: |
<font color='red'>[000:0:1][001:1:3][010:2:3][011:2:4]</font> | <font color='red'>[000:0:1][001:1:3][010:2:3][011:2:4]</font> | ||
Revision as of 10:22, 17 October 2010
Contents |
Introduction
We design and develop a software tool, iGame, which supports database in MoDeL format, to perform task of automatic modeling. Actually, automatic modeling is a database-dependent network-searching-and-developing process from the initial conditions. Besides the database, users are required to provide initial environment condition, such as initial plasmids with biobrick parts, and behaviors of external driven sources, such as temperature controlling system. iGame will generate the network of the biological system in SBML standard. Please refer to user interface to know more about input and output of iGame.
Algorithms for automatic modeling are shown below. Section Algorithm flow chart gives an overall description of the general framework of our algorithms; Section Special reactions: transcription and translation tells details about model of transcription and translation reactions; Section Chain Sorting and Weighting Scheme provides details of sorting as well as weighting scheme and their functions; Section Structural pattern match of template species provides details of the core algorithm of iGame: how to find matchings between template species defined in database and species existed in the bio-system; Section Generation of products based on reaction templates tells method to generate products.
Algorithm flow chart
To complete the final network from initial environment conditions, we first break up the task to several parts:
(1) Setup initial conditions and environmental parameters read from the input file.
(2) Species produced are inserted into a list in the order of time. For each species, we search the database to find template species which could be matched to this species in structural pattern. If not found, then go for the next species.
(3) For each template species we found, we continue to search template reactions containing this template species as a reactant or modifier or both. Only forward or reverse reaction is handled, never for both.
(4) For each template reaction found, we search in the species list for possible species which could be instances of templates of other reactants and modifiers. If not found, then go for next reaction.
(5) For each possible combination of reactants and modifiers, if the reaction parameter conditions are satisfied, we generate the structure of products based on the transfer table and structural templates of products. And then add this new reaction to the reaction list.
(6) Go to step 2 until the end of the species list.
In the following, we will focus on the step (2), (3) and (5). Our algorithms are totally different with that of other software tools since we design them for the purpose of proving the feasibility of MoDeL for synthetic biology. They are kind of complicated because the complexity of biological systems require so.
Special reactions: transcription and translation
Transcription and translation reactions are not supported by MoDeL reaction definitions; they are handled specially in the core program. We use pseudo first-order reaction to model both transcription and translation reactions (RNA polymerase are ignored). The rate constant k is the value of forwardPromoterEfficiency/reversePromoterEfficiency for transcriptions and forwardRbsEfficiency/reverseRbsEfficiency for translations defined for each part in the database. A transcription will not end at a terminator with termination efficiency less than 100% (values are stored in attribute forwardTerminatorEfficiency/reverseTerminatorEfficiency): RNA polymerase will pass over and continue transcription. For translation reactions, the prerequisite condition is that the part next to RBS along the 5' to 3' direction must have non-zero attribute value forwardStartCodon/reverseStartCodon. Opposite to transcriptions, translation reactions would stop if one part with non-zero attribute value forwardStopCodon/reverseStopCodon is encountered.
Chain Sorting and Weighting Scheme
Chains in our Chain-Node Model should not have any order since there are no natural ways to sort them. One chain is not preferred to another, since in a complex of multiple chains, which are connected via binding interaction of binding bites on their own, all chains are equivalent. However, a chain-sorting program is a prerequisite for implementations of many other functions, such as comparison of two Chain-Node structures, or pattern matching of template species to those in the real system.
Sorting is always performed under some rules. Since there are no natural options, we design one to generate the unique order for a list of chains. The rule we developed is something like that for comparing two strings: compare the first part of two chains by their partReference and partType in alphabet order and if equal, then compare the next until there are differences or to the end of either chain. At this stage, two parts are considered as equal if both are in bound state or not. There are some exceptions for DNA molecule: since dsDNA has both forward and reverse directions, comparison between its forward and reverse chain is also needed.
If all chains are different in the first stage of sorting, we have already obtain the unique order of the chain list. However, it is not always so: equal chains in the above sorting may be equivalent or not. It is due to the assumption that two bound parts are taken as equal. Though the above sorting strategy takes binding positions into consideration, it ignores the binding details of those parts: the details are hidden in the nodes of all trees. Hence, similar to the chain sorting, we need to find another strategy to sort nodes as well as trees. Our weighting scheme will be first introduced below.
Assume the chains are sorted already. Each part will be assigned a weight based on its position in the chain list. The weight of the jth part on the ith chain is (i,j). For example, the first part on the first chain posses a weight (0,0) (in C style, counting number from zero). After assignment of parts' weight, we turn to weights of the nodes in trees. Since leaf nodes in trees are actually the representation of parts in bound state on chains, the weight of each leaf node could be inherited from the weight of its corresponding part. For parent node, its weight equals to the maximum of weights of all its children nodes (we define a weight (i, j) is greater than another (i',j') if i < i' or i = i' while j < j'). The recursive definition of nodes' weight of trees makes it possible to sort all children nodes of each node, which is a prerequisite for generating Huffman codes (see below). And then the tree order in the forest could be uniquely determined by sorting the root node of each tree.
Back to the question above, if two chains are equal in the first stage sorting, which should be arranged in front of the other? The answer could be obtained by exchanging them. The exchange will change the parts' weight on both chains and thus the weight of some nodes of the trees. The tree structure is also possible to change. If the tree structure is not changed, the two chains are equivalent, which means that it makes no difference to arrange either chain in front of the other. If the tree structure changes, we must find some ways to determine which tree structure is preferred and based on this to arrange them. We know each tree could be uniquely converted to a binary tree by taking the first child of each node as the left child and its siblings as its right child. The Huffman algorithm is used to generate the Huffman code of each node in the binary tree. Since the Huffman code of each node represents its path to the root node, we can restore the tree structure from the Huffman codes of all leaf nodes. Hence, the Huffman codes of leaf nodes could uniquely determine a tree structure. We could generate a string, unicode_t for tree structure by splicing the Huffman codes and their weight of all leaf nodes sorted by their weights and adding a asterisk between two adjacent codes, for example:
[000:0:1][001:1:3][010:2:3][011:2:4]
Based on this idea, we could obtain the tree unicode_t for any possible order by exchanging equivalent chains and choose the order which make the minimum unicode_t value. By checking the unicode_t value of permutation, chains are grouped in a number of equivalent classes, which contains one or more chains. Chains within each equivalent classes are equivalent: exchanging order of any two chains will not change the tree structure.
It is easy to compare two Chain-Model structures with the help of chain sorting. We only need to compare unicode_c value of chains in the chain list and unicode_t value generated under that order. If two structures are equal, their chain list and tree structure must be equal since the chains order is unique in our chain sorting method. If two structures have same unicode_c value of each chain and unicode_t value, they must be same structures since we could uniquely generate a Chain-Node structure from the strings.
Structural pattern match of template species
We assume that if a combination of species in the species list could be structurally matched to reactants and modifiers templates defined within a reaction, they are possible to react with each other in the way as the reaction template describes. Hence, it is important to find such matchings between species in the species list and template ones defined in the database. We will first give the basic idea and then some modifications.
The basic idea is simple. We first consider the structural pattern matching between one chain and a chain template. There are two kind of parts on a chain template: substituent-type part (ST) and non-substituent-type part (NST). The whole template chain could be separated into blocks of ST parts and NST parts. Then we could break down the task to the matching of each small block. For each NST type block, we find all its matching regions on the chain to be matched, there may be more than one region. Each of the combinations of all NST blocks forms a NST frame and restricts the matching regions of ST blocks. Therefore, the minimal task is to find matchings of each ST part block within a restricted region on the chain to be matched. At the present version of MoDeL, there are 6 ST part: ANY, ANYUB, NZ, NZUB, ONE and ONEUB. A general algorithm for all 6 type part is designed and we will illustrate this via an example. Consider a ST block with all ANY type parts (we use X to indicate ANY type part in the figures). We find matchings of the first part of the block. There may be many possible matchings because part of type ANY implies arbitrary matching of parts on one chain in MoDeL definitions. For each matching found, we deal with the next, and do the same thing recursively until the end of the template or matching fails. An easy example is shown in the figure to illustrate this simple idea.
After all possible matchings for each chain in the template have been found, we could choose any one from each to form a combination. Matching alternatives of two different chains in the template should not be the same. For example, there are two chains in the template, T1 and T2, and three chains, C1, C2 and C3 in the species. If T1 has one matching to C1 and one to C2 and T2 has one to C2 and one to C3, the possible matchings are (T1,T2)->(C1, C2), (T1,T2)->(C1,C3) and (T1,T2)->(T2,T3). (T1,T2)->(C2,C2) is not allowed. (这里已修改)This is based on the assumption that the writer of template is always sure about the structure, he won't write a two-chain template if the parts are actually on one chain. The general matching relations could be written as (n1,n2,n3...)->(m1,m2,m3...), where (n1,n2,n3...) represents chains in the template and (m1,m2,m3...) represents the chains matched in the species for (n1,n2,n3...) respectively. However, it is only part of the matching relation because details, such as the matching positions of parts in the template, are ignored. The next question is: how to validate each matching?
As defined in Chain-Node model, details of distribution of binding are stored in the forest. Matching of chains could not solely determine the overall match -- whether the template and the species have the same structural pattern. However, it is not easy to compare tree structure directly. We designed an algorithm to do this based on the principle: If the template and species have the same structural pattern, it must be possible to isolate the template from the species after replacing the ST part with its matchings. We first replace the ST part of the template with its matchings in the species. And then, we remove the chains which are not matched and the associated trees -- containing leaf nodes whose corresponding parts are on those chains. If the species after removing has the same Chain-Node structure with the template after replacing, the template and the species have the same structural pattern and in brief, the template could be matched to the species. We also illustrate this idea in figures.
However, there is one problem of this algorithm. Consider a LacI dimer template, whose Chain-Node model has two chains with one part on each and one tree with 2 leaf nodes. And there is also a LacI dimer species, it has the same structural pattern with the template. The matching should be (T1,T2)->(C1,C2) and (T1,T2)->(C2,C1) according to the algorithm described above. However, there is indeed one matching since the two matchings are the same. The underlying reason is that the two chains of the template are equivalent: it makes no difference to the tree structure (Huffman code of each node) if they are exchanged. Hence, several equivalent chains should be matched to a certain set of chains in the species only once.
Generation of products based on reaction templates
In MoDeL frame, products are composed of both definite parts and ST parts. The sources of ST parts are defined in component listOfTransferTable. It seems to be very easy to generate Chain-Node structure of products from reactants and mod modifiers based on the transfer table. However, it doesn't.
Consider first a template reaction with one reactant, A-B, where A and B are both NST parts. If it could be digested by a certain enzyme, the products should be A and B. In the real biological system, if there is a species with structure C-A-B-C, where the first part C and the last C binds to form a tree node. If we try to digest the A-B bond, the species would not be split into two pieces as expected because the two products as expected are connected by the tree node. To find products with correct structure, we design a three-step mix-trim-split algorithm to solve this problem.
The first step is to mix reactants and products. The mixture includes all chains of reactants except for those which are matched for some template chain as well as all trees. It also includes all chains and trees of products. And now we have a mixed species with chains and trees from different sources. It is worth noting that chains and trees of modifiers will not be added into the mixture. The next step is to trim the trees. Trees with leaf nodes that are not defined in chains will be removed from the forest. The last step is to split the products out from the mixture. This is because the mixture may not be one standalone complex. In other words, some chains that are not connected with others via tree nodes should not be incorporated into other species. The final standalone split species are real products in the system.
We provide an example to illustrate the product-generating procedure. The reactant has two chains, A-B-C and D-E-F. A, B, C bind with D, E, F, respectively. The products are A and C. First we mix chains and trees. Chain A-B-C will not appear in the mixture. Since node B does not appear in mixed chains, tree with nodes B and E will be removed in the trim process. Because part C and F, A and D, are both bound to nodes, the final product should contain A and B both after split processing.
In the example above, there is only one product finally though two product templates are defined in database. In this case, the corresponding reverse reaction would never be found because it fails to match two templates to only one species. This is a drawback of our MoDeL language -- it does not support description of intra-molecular reactions. If A and C could react as different parts of the product, the reverse reactions would not be lost. However, supporting intra-molecular reactions is one of our future plans for refinement of our MoDeL language.
