Complex chemical substructure search query building and execution

Patent metadata

Field	Value
Publication number	US-10318526-B2
Application number	US-201615202439-A
Country	US
Kind code	B2
Filing date	Jul 5, 2016
Priority date	Jul 5, 2016
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

Systems and methods for enabling construction of complex Boolean chemical substructure queries in a structured graphical user interface are provided. The chemical substructures (molecules) may be represented graphically in standard molecular notation, and may be arranged horizontally and vertically on the interface, along with Boolean logical operators. Boolean logical operators of a first type may logically associate molecules arranged in horizontal fashion to form row queries, whereas Boolean logical operators of a different, second type may logically associate the row queries to form a composite query to be applied to a database of molecules. The operators of the first type may comprise disjunctive operators, whereas the operators of the second type may comprise conjunctive operators.

First claim

What is claimed is:

1. A computer-implemented method for providing representations of chemical compounds in response to a Boolean chemical substructure search query of at least one molecule database, the method comprising:
receiving data representing a Boolean combination of graphical representations of chemical substructures arranged in two or more rows of a graphical user interface, wherein
associated with graphical representations of chemical substructures arranged in rows of the graphical user interface are logical operators representing logical combinations of a first type,
associated with at least two rows of the graphical user interface is at least one logical operator representing at least one logical combination of a second type, and
non-graphical chemical substructure representations correspond to the graphical representations of the chemical substructures;

for each row having graphical substructure representations associated with at least one logical operator of a first type, combining each such first-type logical operator and its associated non-graphical substructure representations into a row sub-query, wherein each logical operator is associated with at most two non-graphical substructure representations in accordance with the Boolean combination;
for each row, combining the row sub-queries into a row query in accordance with the Boolean combination;
combining the row queries with the at least one second-type logical operator in accordance with the Boolean combination to generate a composite search query;
executing the composite search query by applying the logical operators to the non-graphical substructure representations in accordance with the Boolean combination to produce Boolean query results comprising one or more chemical structures representing chemical compounds; and
providing for graphical display the Boolean query results.

2. The method of claim 1 , wherein
if a row contains two or more two non-graphical chemical substructure representations, the row is characterized as containing one or more unique pairs of non-graphical chemical substructure representations wherein each non-graphical chemical substructure representation may be a member of only one unique pair, and
combining each first-type logical operator and its associated non-graphical substructure representations into a row sub-query comprises:
combining every adjacent unique pair of non-graphical chemical substructure representations in the row with its associated first-type logical operator to form a row sub-query for each pair; and
combining any single uncombined non-graphical chemical substructure representation in the row with any uncombined first-type logical operator to form a row sub-query for the uncombined non-graphical chemical substructure representation.

3. The method of claim 1 , wherein
each of the non-graphical representations resides in a tree data structure at an operand node that is related to at most one other operand node by a logical operator in accordance with the Boolean combination, and
combining each first-type logical operator and its associated non-graphical representations into a row sub-query comprises combining each first-type logical operator and its related operand nodes into the row sub-query.

4. The method of claim 3 , further comprising recursively traversing the tree data structure to generate a text-based database query to serve as the composite search query.

5. The method of claim 3 , the method further comprising:
storing the operand nodes in a first database table;
storing the logical operators in a second database table; and
storing relationships among the logical operators and the operand nodes in a join table,
wherein executing the composite search query comprises performing database operations on the operand nodes in the first database table using the logical operators in the second database table.

6. The method of claim 5 , wherein storing each operand node in a database table includes storing, for at least one operand node, an indication of the number of instances of the chemical substructure corresponding to the at least one operand node to be searched in the at least one molecule database.

7. The method of claim 1 , wherein combining the row queries comprises:
combining each second-type logical operator with associated row queries to generate, for each second-type logical operator, a column sub-query, wherein each second-type logical operator is associated with at most two row queries; and
combining the column sub-queries to generate the composite search query.

8. The method of claim 1 , wherein the logical combinations of the first type consist of disjunctive operations, and the logical combinations of the second type consist of conjunctive operations.

9. The method of claim 1 , wherein the received data further comprises data representing at least one numerical constraint indicator, each numerical constraint indicator indicating a number of instances of a corresponding chemical substructure to be searched for in the at least one molecule database.

10. A computer-implemented method for providing representations of chemical compounds in response to a Boolean chemical substructure search query of at least one molecule database, the method comprising:
receiving data representing a Boolean combination of graphical representations of chemical substructures arranged in two or more rows of a graphical user interface, wherein
associated with graphical representations of chemical substructures arranged in rows of the user interface are logical operators representing logical combinations of a first type, and
associated with at least two rows of the user interface is at least one logical operator representing at least one logical combination of a second type, and
non-graphical chemical substructure representations correspond to the graphical representations of the chemical substructures;

traversing a tree data structure representing the Boolean chemical substructure search query to generate a text-based query,
wherein the tree data structure includes a plurality of sub-query structures each comprising (a) a logical operator node representing one of the logical operators of the first type or the second type and (b) at most two child nodes, in accordance with the Boolean combination,
wherein the at most two child nodes of a sub-query structure comprise one of the following sets: two operand nodes, an operand node and another sub-query structure, or two other sub-query structures, and
wherein an operand node represents a non-graphical substructure representation;
executing the text-based query by applying the logical operators to the non-graphical substructure representations in accordance with the Boolean combination to produce Boolean query results comprising one or more chemical structures representing chemical compounds; and
providing for graphical display the Boolean query results.

11. The method of claim 10 , wherein the user interface resides at a client computing device, and a server performs the traversal of the tree data structure, the method further comprising the server translating the non-graphical representations into the operand nodes of the tree data structure.

12. The method of claim 10 , wherein the user interface resides at a client computing device, and a server performs the traversal of the tree data structure, the method further comprising the client computing device translating the non-graphical representations into the operand nodes of the tree data structure.

13. The method of claim 10 , further comprising:
forming the logical operator nodes;
forming the operand nodes;
for

Assignees

• Zymergen Inc

Inventors

• Dean Jed
• Safir Adam
• Werner Gregory Michael

Classifications

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F19/709

  Physics · mapped topic

• G06F16/2428 Primary

  Query predicate definition using graphical user interfaces, including menus and forms (G06F16/2423 takes precedence) · CPC title