CN104820767B - The component method for arranging and system of biochemical reaction detection means on micro chip - Google Patents
The component method for arranging and system of biochemical reaction detection means on micro chip Download PDFInfo
- Publication number
- CN104820767B CN104820767B CN201510280749.0A CN201510280749A CN104820767B CN 104820767 B CN104820767 B CN 104820767B CN 201510280749 A CN201510280749 A CN 201510280749A CN 104820767 B CN104820767 B CN 104820767B
- Authority
- CN
- China
- Prior art keywords
- ilp
- component
- guess value
- kth
- layout
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Landscapes
- Apparatus Associated With Microorganisms And Enzymes (AREA)
- Medicines Containing Antibodies Or Antigens For Use As Internal Diagnostic Agents (AREA)
Abstract
The first aspect of the invention is to provide the component method for arranging and system of biochemical reaction detection means on a kind of micro chip, including：The conjecture value recursive rule of integral linear programming ILP constraints and setting reaction deadline are designed, the constraints includes reaction deadline constraints；Kth time conjecture value is calculated according to the conjecture value recursive rule and substitutes into the kth time reaction deadline constraints composition kth time ILP constraintss, joint solves and judges whether ILP corresponding to the kth time conjecture value is feasible under the kth time constraints；The ILP upper bounds solved are updated to the kth time conjecture value if feasible, the ILP lower bounds solved are updated to the kth time conjecture value if infeasible；Iteration said process is until the last solution for trying to achieve ILP is laid out for module position.The method of the invention can reduce the time of whole biochemical reaction detection process by the physical location and its access path that rationally design component.
Description
Technical Field
The invention belongs to the field of biochemical reaction detection, and particularly relates to a component arrangement method and a component arrangement system of a biochemical reaction detection device on a microchip.
Background
In the existing biochip (Bio-chip), because on-chip reaction resources are limited, whether the component layout reasonably and directly affects the detection completion time, and in order to better utilize the limited on-chip resources for different detections to reduce the detection time, a reasonable physical position layout of the components and a layout scheme of connection paths thereof need to be set.
Disclosure of Invention
The invention provides a component arrangement method and a component arrangement system of a biochemical reaction detection device on a microchip, which are used for reducing the time of the whole biochemical reaction detection process by reasonably designing the physical position of a component and a connection path thereof.
A first aspect of the present invention provides a method for arranging components of a biochemical reaction detecting apparatus on a microchip, comprising:
designing constraint conditions of integer linear programming ILP and setting a guess value recursion rule of reaction completion time, wherein the constraint conditions comprise the constraint conditions of the reaction completion time;
calculating according to the guess value recursion rule to obtain a kth guess value, substituting the kth guess value into the reaction completion time constraint condition to form a kth ILP constraint condition, and performing combined solution under the kth constraint condition to judge whether the ILP corresponding to the kth guess value is feasible or not;
if the value is feasible, updating the upper bound of the ILP solution to the k-th guess value, and if the value is not feasible, updating the lower bound of the ILP solution to the k-th guess value;
and iterating the calculation to obtain a k-th guess value, solving and judging whether the corresponding ILP is feasible and updating the ILP upper limit or lower limit until the final solution of the ILP is the component position layout.
In a second aspect of the present invention, there is provided a component arrangement system for a biochemical reaction detecting apparatus on a microchip, comprising:
a position layout module, configured to design constraint conditions of an integer linear programming ILP and set guess value recurrence rules of response completion time, where the constraint conditions include response completion time constraint conditions, calculate a kth guess value according to the guess value recurrence rules, substitute the kth guess value into the kth response completion time constraint conditions to form kth ILP constraint conditions, jointly solve and determine whether ILP corresponding to the kth guess value is feasible under the kth constraint conditions, update an upper bound of an ILP solution to the kth guess value when feasible, update a lower bound of the ILP solution to the kth guess value when infeasible, iterate the calculation to obtain the kth guess value, determine whether ILP is feasible and solve the process of updating the upper bound or the lower bound of the ILP until a final solution of the ILP is obtained, and output a component position layout and component routing composition component layout scheme;
and the routing layout module is used for calculating and obtaining the routing layout under the component position layout according to a maze algorithm.
The invention has the beneficial effects that:
the component arrangement method of the biochemical reaction detection device on the microchip designs the biochip by adopting an ILP (Integer Linear Programming) algorithm, namely, the limiting conditions of the component position and the limiting conditions of the biochemical reaction completion sequence are set as the constraint conditions of the ILP when the biochip is designed, the ILP containing unknown constraint of biochemical reaction completion time is solved by successive iteration to reduce the upper bound and the lower bound of the ILP solution, the final solution is obtained to give the component position layout, and the time of the whole biochemical reaction detection process is reduced by reasonably designing the physical position and the connection path of the component; particularly, in iteration, a geometric series updating method is used for replacing a dichotomy in the conventional ILP for a guessed value of the biochemical reaction completion time, so that the solving time is reduced, and the design speed for different detection process component arrangements is improved.
Drawings
FIG. 1 is a flow chart showing a first embodiment of a method for arranging elements of the on-chip biochemical reaction detecting apparatus according to the present invention;
FIG. 2 is a block diagram of a component arrangement system according to a first embodiment of the present invention.
Detailed Description
FIG. 1 is a flowchart of a first embodiment of a method for arranging elements of a biochemical reaction detecting device on a microchip according to the present invention, as shown in FIG. 1, the method for arranging elements of the biochemical reaction detecting device on a microchip according to the present invention comprises:
s101, designing constraint conditions of integer linear programming ILP (integer Linear programming) and setting a guess value recursion rule of reaction completion time, wherein the constraint conditions comprise the constraint conditions of the reaction completion time;
preferably, the ILP constraints (1) to (4) include:
constraint (1) that a component corresponds to and only one physical location:
component non-overlapping constraint (2):
component resource constraint (3):
the constraint condition indicates that at a time node t, the sum of the demands of j-th resources corresponding to all biochemical reactions needing the j-th resources is not more than the total amount of the j-th resources;
biochemical reaction sequence constraint (4):
wherein, a x,y,t,i Representing the corresponding layout variable of the component, the layout variable a x,y,t,i X, y, t and i in the database respectively represent two physical position coordinates of the component, a time node of the component in the biochemical reaction process and a component identifier;representing the amount of j resources required by the i component, r j Represents the total amount of j-th resources; t represents the total time for completion of the biochemical reaction; i.e. the constraint (5) for solving ILP jointly:
preferably, the assembly comprises an input liquid storage tank, an output liquid storage tank and a dilution tank for detecting the biochemical reactant on the microchip;
preferably, the assembly further comprises an Optical Sensor (Optical Sensor) for detecting a biochemical reactant on the microchip;
preferably, the guessed value recurrence rule of the reaction completion time includes:
setting the first guess as the initial guess t 0 ；
Or,
updating the k-th guess value t according to the formula (6) k ：
Wherein k is>1，U k-1 Represents the upper bound, L, of the ILP solution for the (k-1) th iteration k-1 Represents the lower bound of the ILP solution for the (k-1) th iteration;
correspondingly, the iterating the calculation to obtain the k-th guess, the solving to judge whether the corresponding ILP is feasible, and the updating the ILP upper bound or lower bound process until the final solution of the ILP is obtained include:
iterating the calculation to obtain a k-th guess value, solving and judging whether the corresponding ILP is feasible or not, and updating the ILP upper bound or lower bound process until the iteration number n meets the requirement (7):
n＝loglog(U n-1 /L n-1 ) (7)；
wherein, U n-1 Represents the upper bound, L, of the ILP solution for the (n-1) th iteration n-1 Represents the lower bound of the ILP solution for the (n-1) th iteration;
s102, calculating according to the guess value recursion rule to obtain a kth guess value, substituting the kth guess value into the reaction completion time constraint condition to form a kth ILP constraint condition, and jointly solving under the kth constraint condition and judging whether the ILP corresponding to the kth guess value is feasible or not;
s103, if the upper bound of the ILP solution is feasible, updating the upper bound of the ILP solution to the k-th guessed value, and if the lower bound of the ILP solution is not feasible, updating the lower bound of the ILP solution to the k-th guessed value, and keeping the upper bound of the ILP solution unchanged;
s104, iterating the calculation to obtain a k-th guess value, solving and judging whether the corresponding ILP is feasible or not and updating the ILP upper bound or lower bound process until the final ILP solution is obtained and is the component position layout;
preferably, after iterating the calculation to obtain the kth guess value, solving to determine whether the corresponding ILP is feasible, and updating the ILP upper bound or lower bound until the final ILP solution is determined as the component position layout, the method further includes:
and S105, calculating a route layout under the component position layout according to a maze algorithm, wherein the component position layout and the component route layout form an output scheme of the component layout.
In the first embodiment of the component arrangement method of the biochemical reaction detection device on the microchip of the present invention, the biochip is designed by using the ILP (Integer Linear programming), that is, the limiting conditions of the component arrangement and the limiting conditions of the biochemical reaction completion sequence are set as the constraint conditions of the ILP when the biochip is designed, and the ILP containing the unknown constraint of the biochemical reaction completion time is solved by successive iteration to reduce the upper bound and the lower bound of the solution of the ILP, so that the final solution is obtained to give the component position layout, thereby realizing the reduction of the time of the whole biochemical reaction detection process by reasonably designing the physical position of the component and the connection path thereof; particularly, in iteration, a geometric series updating method is used for replacing a dichotomy in the existing ILP for a guessed value of the biochemical reaction completion time, so that the solving time is reduced, and the design speed for different detection process component arrangements is improved.
FIG. 2 is a flow chart of a first embodiment of a component arrangement system of a biochemical reaction detecting apparatus on a microchip according to the present invention, as shown in FIG. 2, the component arrangement system of the biochemical reaction detecting apparatus on a microchip according to the present invention comprises:
a position layout module 21, configured to design constraint conditions of an integer linear programming ILP and set guess value recurrence rules of response completion time, where the constraint conditions include response completion time constraint conditions, calculate a kth guess value according to the guess value recurrence rules, substitute the kth guess value into the response completion time constraint conditions to form kth-time ILP constraint conditions, jointly solve and determine whether ILP corresponding to the kth guess value is feasible under the kth constraint conditions, update an upper bound of ILP solution to the kth guess value (and a lower bound of ILP solution is unchanged) when feasible, update a lower bound of ILP solution to the kth guess value (and an upper bound of ILP solution is unchanged) when infeasible, and iterate the calculation to obtain the kth guess value, determine whether ILP is feasible by the solution, and iterate a process of updating the upper bound or the lower bound of ILP until a final solution of ILP is obtained, and output a component layout scheme composed of component position and component routes;
and the routing layout module is used for calculating and obtaining the routing layout under the component position layout according to a maze algorithm.
Preferably, the ILP constraints (1) to (4) include:
constraint (1) that a component corresponds to and only one physical location:
component non-overlap constraint (2):
component resource constraint (3):
the constraint condition indicates that at a time node t, the sum of the demanded quantity of j-th resources corresponding to all biochemical reactions needing the j-th resources is not more than the total quantity of the j-th resources;
biochemical reaction sequence constraint (4):
i.e. the constraint (5) for jointly solving ILP:
wherein, a x,y,t,i Representing the corresponding layout variable of the component, the layout variable a x,y,t,i X, y, t and i in the database respectively represent two physical position coordinates of the component, a time node of the component in the biochemical reaction process and a component identifier;representing the amount of j resources required by the i component, r j Represents the total amount of j-th resources; t represents the total time for completion of the biochemical reaction.
Preferably, the guessed value recurrence rule of the reaction completion time includes:
setting a first guess value t 0 (i.e., the initial guess);
or,
updating the k-th guess value t according to the formula (6) k ：
Wherein k is>1，U k-1 Represents the upper bound, L, of the ILP solution for the (k-1) th iteration k-1 Representing the lower bound of the ILP solution for the (k-1) th iteration.
Finally, it should be noted that: the above embodiments are only used to illustrate the technical solution of the present invention, and not to limit the same; while the invention has been described in detail and with reference to the foregoing embodiments, it will be understood by those skilled in the art that: the technical solutions described in the foregoing embodiments may still be modified, or some or all of the technical features may be equivalently replaced; and these modifications or substitutions do not depart from the spirit of the corresponding technical solutions of the embodiments of the present invention.
Claims (6)
1. A method for arranging components of a biochemical reaction detecting apparatus on a microchip, comprising:
designing constraint conditions of integer linear programming ILP and setting a guess value recursion rule of reaction completion time, wherein the constraint conditions comprise the constraint conditions of the reaction completion time;
calculating according to the guess value recursion rule to obtain a kth guess value, substituting the kth guess value into the reaction completion time constraint condition to form a kth ILP constraint condition, and performing combined solution under the kth constraint condition to judge whether the ILP corresponding to the kth guess value is feasible or not;
if feasible, updating the upper bound of the ILP solution to the k-th guess value, and if infeasible, updating the lower bound of the ILP solution to the k-th guess value;
iterating the calculation to obtain a k-th guess value, solving and judging whether the corresponding ILP is feasible or not and updating the ILP upper bound or lower bound process until the final ILP solution is obtained as the component position layout;
wherein,
the ILP constraints include:
constraint (1) that a component corresponds to and only one physical location:
component non-overlapping constraint (2):
component resource constraint (3):
biochemical reaction sequence constraint (4):
a x,y,t,i representing the corresponding layout variable of the component, the layout variable a x,y,t,i X, y, t and i in the formula (I) respectively represent two physical position coordinates of the component, a time node of the component in the biochemical reaction process and a component identifier;denotes the amount of j-th resource, r, required by the i-th component j Represents the total amount of j-th resources; t represents the total time for completion of the biochemical reaction;
the guess value recurrence rule comprises:
setting a first guess value t 0 ；
Or,
updating the k-th guess value t according to the formula (6) k ：
k>1，U k-1 Represents the upper bound, L, of the ILP solution for the (k-1) th iteration k-1 Representing the lower bound of the ILP solution for the (k-1) th iteration.
2. The method of claim 1, wherein the iterating the calculating to obtain the k-th guess, the solving to determine whether the corresponding ILP is feasible, and the updating the ILP upper or lower bound process until the final ILP solution is obtained comprises:
iterating the calculation to obtain a k-th guess value, solving and judging whether the corresponding ILP is feasible or not and updating the ILP upper bound or lower bound process until the iteration number n meets (7):
n＝log log(U n-1 /L n-1 ) (7)；
wherein, U n-1 Representing the (n-1) th iterationUpper bound of ILP solution, L n-1 Representing the lower bound of the ILP solution for the (n-1) th iteration.
3. The method for arranging the modules of a biochemical reaction detecting apparatus on a microchip according to claim 1, wherein the modules comprise an input reservoir, an output reservoir and a diluting well for detecting biochemical reactants on the microchip.
4. The method of claim 3, wherein the assembly further comprises an optical sensor for detecting the biochemical reactant on the microchip.
5. The method as claimed in claim 1, further comprising, after the iterating the calculating to obtain the k-th guess, the solving to determine whether the corresponding ILP is feasible, and the updating the ILP upper or lower bound until the final ILP solution is found to be the component position layout:
and calculating to obtain a routing layout under the component position layout according to a maze algorithm, wherein the component position layout and the component routing layout form an output scheme of component layout.
6. A component placement system for a biochemical reaction detecting apparatus on a microchip, comprising:
a position layout module, configured to design constraint conditions of an integer linear programming ILP and set guess value recurrence rules of response completion time, where the constraint conditions include response completion time constraint conditions, calculate a kth guess value according to the guess value recurrence rules, substitute the kth guess value into the kth response completion time constraint conditions to form kth ILP constraint conditions, jointly solve and determine whether ILP corresponding to the kth guess value is feasible under the kth constraint conditions, update an upper bound of an ILP solution to the kth guess value when feasible, update a lower bound of the ILP solution to the kth guess value when infeasible, iterate the calculation to obtain the kth guess value, determine whether ILP is feasible and solve the process of updating the upper bound or the lower bound of the ILP until a final solution of the ILP is obtained, and output a component position layout and component routing composition component layout scheme;
the routing layout module is used for calculating and obtaining the routing layout under the component position layout according to a maze algorithm;
wherein,
the ILP constraints include:
constraint (1) that a component corresponds to and only one physical location:
component non-overlap constraint (2):
component resource constraint (3):
biochemical reaction sequence constraint (4):
a x,y,t,i representing the corresponding layout variable of the component, the layout variable a x,y,t,i X, y, t and i in the formula (I) respectively represent two physical position coordinates of the component, a time node of the component in the biochemical reaction process and a component identifier;denotes the amount of j-th resource, r, required by the i-th component j Represents the total amount of j-th resources; t representsTotal time for completion of biochemical reactions;
the guess value recurrence rule comprises:
setting a first guess value t 0 ；
Or,
updating the k-th guess value t according to the formula (6) k ：
k>1，U k-1 Represents the upper bound, L, of the ILP solution for the (k-1) th iteration k-1 Representing the lower bound of the ILP solution for the (k-1) th iteration.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510280749.0A CN104820767B (en) | 2015-05-27 | 2015-05-27 | The component method for arranging and system of biochemical reaction detection means on micro chip |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510280749.0A CN104820767B (en) | 2015-05-27 | 2015-05-27 | The component method for arranging and system of biochemical reaction detection means on micro chip |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104820767A CN104820767A (en) | 2015-08-05 |
| CN104820767B true CN104820767B (en) | 2018-01-26 |
Family
ID=53731062
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510280749.0A Expired - Fee Related CN104820767B (en) | 2015-05-27 | 2015-05-27 | The component method for arranging and system of biochemical reaction detection means on micro chip |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104820767B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106611084B (en) * | 2016-11-29 | 2020-12-18 | 北京集创北方科技股份有限公司 | Design method and device of integrated circuit |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102004833A (en) * | 2010-11-25 | 2011-04-06 | 中南大学 | Generating method of virtual mask for genetic chip in-situ synthesis |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8685325B2 (en) * | 2010-03-09 | 2014-04-01 | Sparkle Power Inc. | Field-programmable lab-on-a-chip based on microelectrode array architecture |
-
2015
- 2015-05-27 CN CN201510280749.0A patent/CN104820767B/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102004833A (en) * | 2010-11-25 | 2011-04-06 | 中南大学 | Generating method of virtual mask for genetic chip in-situ synthesis |
Non-Patent Citations (2)
| Title |
|---|
| Testing and Diagnosis of Realistic Defects in Digital Microfluidic Biochips;FEI SU 等;《JOURNAL OF ELECTRONIC TESTING: Theory and Applications》;20071231;第219-233页 * |
| 基于三链DNA结构的0-1整数规划;杨静;《中国优秀硕士学位论文全文数据库 信息科技辑》;20090315(第3期);第I137-51页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104820767A (en) | 2015-08-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Diniz-Filho et al. | Darwinian shortfalls in biodiversity conservation | |
| Iwata et al. | AntMap: constructing genetic linkage maps using an ant colony optimization algorithm | |
| Weinstein et al. | Taxonomic, phylogenetic, and trait beta diversity in South American hummingbirds | |
| Che et al. | Cyclic hoist scheduling in large real-life electroplating lines | |
| CN110988269B (en) | Deviation correction method and device for atmospheric pollution source emission list and storage medium | |
| US8397204B2 (en) | System and methodology for development of a system architecture using optimization parameters | |
| CN106503333B (en) | A three-dimensional network-on-chip test planning method | |
| Pan et al. | An iterative method for design of water‐using networks with regeneration recycling | |
| CN103309805A (en) | Automatic selection method for test target in object-oriented software under xUnit framework | |
| CN104820767B (en) | The component method for arranging and system of biochemical reaction detection means on micro chip | |
| Zhang et al. | Parasitic-aware optimization and retargeting of analog layouts: A symbolic-template approach | |
| Zhang et al. | Augmenting optimization-based molecular design with graph neural networks | |
| Fakhrmoosavi et al. | An iterative learning approach for network contraction: Path finding problem in stochastic time‐varying networks | |
| Cirstea et al. | Digital electronic system-on-chip design: Methodologies, tools, evolution, and trends | |
| Meng et al. | Automatic design of extractive distillation sequence for a multicomponent azeotropic system | |
| CN104253830B (en) | A kind of location Based service system of selection | |
| Zhang et al. | Optimal synthesis of quaternary zeotropic distillation sequences using an array formulation | |
| JP7592652B2 (en) | Information processing device, information processing method, and program | |
| CN108961071A (en) | The method and terminal device of automatic Prediction composite service income | |
| CN117391014A (en) | Parallel Bayesian circuit optimization method based on heterogeneous model integration | |
| CN107992666A (en) | One kind escape wiring method | |
| Prautsch et al. | Generating the Generator: A User-Driven and Template-Based Approach towards Analog Layout Automation | |
| CN115206431A (en) | Method, device, equipment and storage medium for predicting nitrogen cycle driving factor | |
| CN104881542B (en) | The component method for arranging and system of biochemical reaction detection device on micro chip | |
| Yan et al. | Untangling twisted nets for bus routing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| EXSB | Decision made by sipo to initiate substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| TA01 | Transfer of patent application right | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20171228 Address after: 100045, 1, 16 Hebei street, three li, Beijing, Xicheng District Applicant after: Midtown characteristic town planning Research Institute Co Ltd Address before: 100083 Beijing City, Haidian District Zhongguancun Road No. 18 smartfortune International Building A-605 Applicant before: Hu Shiyan Applicant before: Xie Jun |
|
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20180126 Termination date: 20180527 |