# Designing molecules with cost function networks - Bridging symbolic and numerical AI.

Thomas Schiex

<figure><img src="image_1.png" /></figure>

## To cite this version:

Thomas Schiex. Designing molecules with cost function networks - Bridging symbolic and numerical AI. Journées plénières du GDR IA du CNRS, Oct 2018, Paris, France. hal-02785414

HAL Id: hal-02785414

https://hal.inrae.fr/hal-02785414

Submitted on 4 Jun 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Designing molecules with cost function networks

## Bridging symbolic and numerical AI

T. Schiex

D. Allouche, S. Barbe, J. Cortes, M. Ruffini, D. Simoncini, A. Voet, J. Vucinic

S. de Givry, G. Katsirelos, M. Zytnicki

October 2018
<figure><img src="image_3.png" /></figure>

Constraint network (X, C)

* a sequence X of discrete variables $x_i$, domain $D_i$

Joint feasibility distribution
## Constraint network (X, C)

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set C of constraints

## Joint feasibility distribution
Constraint network (X, C)

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set C of constraints

* $c_S \in C$ involves variables in $S \subseteq X$ and is a boolean function $\prod_{i \in S} D_i \rightarrow \{t, f\}$

Joint feasibility distribution
## Constraint network (X, C)

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set C of constraints

* $c_S \in C$ involves variables in $S \subseteq X$ and is a boolean function $\prod_{i \in S} D_i \rightarrow \{t, f\}$

* Joint boolean function $F(X) = \bigwedge c_S$

## Joint feasibility distribution

## Central problems: SAT/CSP and their solvers

* A solution is an assignment of X that satisfies the joint function (NP-complete)

* Algorithms to find a model/solution or a proof (Backtrack, unit/constraint propagation)
## SAT and CSP technologies

* Solving and generating Sudokus (Le Monde)

* Planning and Scheduling¹²

* Configuration/verification (also neural nets⁵)

* Recent theorem proof (Splitting all pythagorean triples in N: 200 TB proof⁴)

<figure><img src="image_4.png" /></figure>

cnes

(Rosetta-Philae probe plan, CP, LAAS/Toulouse)

SIEMENS

THALES

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>
## SAT and CSP technologies

* Solving and generating Sudokus (Le Monde)

* Planning and Scheduling¹²

* Configuration/verification (also neural nets⁵)

* Recent theorem proof (Splitting all pythagorean triples in N: 200 TB proof⁴)

<figure><img src="image_7.png" /></figure>

(Rosetta-Philae probe plan, CP, LAAS/Toulouse)

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

Excellent to describe, analyze, design perfectly known complex systems.
## SAT and CSP technologies

* Solving and generating Sudokus (Le Monde)

* Planning and Scheduling¹²

* Configuration/verification (also neural nets⁵)

* Recent theorem proof (Splitting all pythagorean triples in N: 200 TB proof⁴)

<figure><img src="image_13.png" /></figure>

(Rosetta-Philae probe plan, CP, LAAS/Toulouse)

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

Excellent to describe, analyze, design perfectly known complex systems.

Biology is full of imperfectly known complex systems.
Cost function network (X, W)

Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$
Cost function network (X, W) Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions
Cost function network (X, W)

Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions

* $w_S \in W$ is a numerical function $\prod_{i \in S} D_i$ (possibly infinite costs)
Cost function network (X, W) Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions

* $w_S \in W$ is a numerical function $\prod_{i \in S} D_i$ (possibly infinite costs)

* Joint cost function $W(X) = \sum w_S$
Cost function network (X, W)

Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions

* $w_S \in W$ is a numerical function $\prod_{i \in S} D_i$ (possibly infinite costs)

* Joint cost function $W(X) = \sum w_S$

* Generalizes CSP/SAT: a constraint is a cost function that maps to {0, $\infty$}
Cost function network (X, W)

Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions

* $w_S \in W$ is a numerical function $\prod_{i \in S} D_i$ (possibly infinite costs)

* Joint cost function $W(X) = \sum w_S$

* Generalizes CSP/SAT: a constraint is a cost function that maps to $\{0, \infty\}$

* **Complex interactions of graduality with comparability** (likelihood, preferences)
Cost function network (X, W)

Joint cost/feasibility distribution²,⁹

* a sequence X of discrete variables $x_i$, domain $D_i$

* a set W of cost functions

* $w_S \in W$ is a numerical function $\prod_{i \in S} D_i$ (possibly infinite costs)

* Joint cost function $W(X) = \sum w_S$

Central problems: PWMaxSAT, WCSP, MAP/MRF

* a solution optimizes the joint cost $W(X)$ (WCSP, NP-complete)

* algorithms to find a solution and a proof of optimality (Branch and bound + cost function propagation, core-based)
Graph $G = (V, E)$ with edge weight function $w$

Graphical model³

* A boolean variable $x_i$ per vertex $i \in V$

* A cost function per edge $e = (i, j) \in E : w_{ij} = w(i, j) \times 1[x_i \neq x_j]$

* Hard edges: constraints with costs 0 or $-\infty$ (when $x_i \neq x_j$)
Example: MAXCUT with hard edges

Graph $G = (V, E)$ with edge weight function $w$

Graphical model³

* A boolean variable $x_i$ per vertex $i \in V$

* A cost function per edge $e = (i, j) \in E : w_{ij} = w(i, j) \times 1[x_i \neq x_j]$

* Hard edges: constraints with costs 0 or $-\infty$ (when $x_i \neq x_j$)

3-clique

* vertices {1, 2, 3}

* cut weight 1

* edge (1, 2) hard.

<figure><img src="image_19.png" /></figure>
Graph $G = (V, E)$ with edge weight function $w$

Graphical model³

* A boolean variable $x_i$ per vertex $i \in V$

* A cost function per edge $e = (i, j) \in E : w_{ij} = w(i, j) \times 1[x_i \neq x_j]$

* Hard edges: constraints with costs 0 or $-\infty$ (when $x_i \neq x_j$)

3-clique

* vertices {1, 2, 3}

* cut weight 1

* edge (1, 2) hard.

<figure><img src="image_20.png" /></figure>
<figure><img src="image_21.png" /></figure>

MAXCUT on a 3-clique with hard edge

```json
{
  "problem" : {"name": "MaxCut", "mustbe": >0.0"},
  "variables": {"x1": ["1","r"], "x2": ["1","r"], "x3": ["1","r"]},
  "functions": {
    "cut12": {"scope": ["x1","x2"], "costs": [0,-100,-100,0]},
    "cut13": {"scope": ["x1","x3"], "costs": [0,1,1,0]},
    "cut23": {"scope": ["x2","x3"], "costs": [0,1,1,0]}
  }
}
```
Can be concisely expressed as

* A set of weighted clauses

* An integer linear program

* A Markov Random Field (stochastic graphical model with additive potentials)

* A quadratic boolean polynomial
<figure><img src="image_22.png" /></figure>

Can be concisely expressed as

* A set of weighted clauses

* An integer linear program

* A Markov Random Field (stochastic graphical model with additive potentials)

* A quadratic boolean polynomial

And the WCSP problem tackled with

* MaxHS (PWMaxSat solver)

* CPLEX/GUROBI (ILP solver)

* MAP/MRF solvers (very few provide guarantees: toulbar2, daoopt)

* A quadratic boolean polynomial (SDP based BiqMac)
## Most active molecules of life

Flexible sequence of “amino-acids”, each chosen among a set of 20 natural ones (or more)

## Folding

<figure><img src="image_23.png" /></figure>

Transporter, binder/regulator, motor, catalyst...

Hemoglobin, TAL effector, ATPase, dehydrogenases...
## Most active molecules of life

Flexible sequence of “amino-acids”, each chosen among a set of 20 natural ones (or more)

## Inverse folding

Function →

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

Transporter, binder/regulator, motor, catalyst...

Hemoglobin, TAL effector, ATPase, dehydrogenases...
<figure><img src="image_27.png" /></figure>

## Eco-friendly chemical/structural nano-agents

* Biodegradable (have been mass produced for billions of year)
<figure><img src="image_28.png" /></figure>

## Eco-friendly chemical/structural nano-agents

* Biodegradable (have been mass produced for billions of year)

* "Easy" to produce (transformed E. coli)
## Eco-friendly chemical/structural nano-agents

* Biodegradable (have been mass produced for billions of year)

* "Easy" to produce (transformed E. coli)

* Useful for green chemistry⁸ (biofuels, plastic recycling, food and feed, cosmetics...), nanotechnologies,¹³ drugs...

20ⁿ sequences!

intractable for experimental techniques
## Molecular modeling

* Full atom model of a protein backbone (assumed to be rigid)

<figure><img src="image_29.png" /></figure>
## Molecular modeling

* Full atom model of a protein backbone (assumed to be rigid)

* Catalog of all 20 side-chains in different conformations (≈ 400 overall)

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>
## Molecular modeling

* Full atom model of a protein backbone (assumed to be rigid)

* Catalog of all 20 side-chains in different conformations (≈ 400 overall)

* Huge sequence-conformation space: 400ⁿ (or more)

<figure><img src="image_32.png" /></figure>
<figure><img src="image_33.png" /></figure>

## Thermodynamics: forces, energy and stability

* Full atom empirical force field (bonds, electrostatics, solvant...)
## Thermodynamics: forces, energy and stability

* Full atom empirical force field (bonds, electrostatics, solvant...)

* Usually decomposed as a sum of pairwise terms that depends on atom positions
## Thermodynamics: forces, energy and stability

* Full atom empirical force field (bonds, electrostatics, solvant...)

* Usually decomposed as a sum of pairwise terms that depends on atom positions

## Imperfect

* Approximations: rigidity, solvent effect

* Very empirical representation of crucial quantum mechanic effects
<table><tr><td>Central problem</td><td>(plenty of tricky/harder variants)</td></tr><tr><td>Maximum stability ≡ Minimum energy</td><td>NP-hard<sup>7</sup></td></tr></table>
<table><tr><td>Central problem</td><td>(plenty of tricky/harder variants)</td></tr><tr><td>Maximum stability ≡ Minimum energy</td><td>NP-hard<sup>7</sup></td></tr></table>

## As a Cost Function Network

* One variable per position in the protein sequence

* Domain: catalog of few hundreds amino acids conformations

* Functions: decomposed energy (pairwise terms)
Toulbar2 vs. CPLEX, MaxHS...(real instances)

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

\# of instances solved (X) within a per instance cpu-time limit (Y)
<figure><img src="image_36.png" /></figure>

Optimality gap of the Simulated annealing solution as problems get harder
Asymptotic convergence can be arbitrarily slow (infinity can be arbitrarily far)
C8 pseudo-symmetric 20VP symmetrized into a nano-component

<figure><img src="image_37.png" /></figure>
C8 pseudo-symmetric 20VP symmetrized into a nano-component

<figure><img src="image_38.png" /></figure>

Tako: (R)evolution + Rosetta/talaris14

8 fold

20VP

<figure><img src="image_39.png" /></figure>

Tako

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>
C8 pseudo-symmetric 20VP symmetrized into a nano-component

<figure><img src="image_43.png" /></figure>

Tako: (R)evolution + Rosetta/talaris14

8 fold

<figure><img src="image_44.png" /></figure>

Ika: toulbar2 + talaris14

4 fold

20VP

<figure><img src="image_45.png" /></figure>

Tako

<figure><img src="image_46.png" /></figure>

Ika

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>
<figure><img src="image_51.png" /></figure>

Compares Tako and Ika structural stability as temperature increases
(circular dichroism)
Imperfect

Simplest way around this: inject more information than just energy.
## Imperfect

Simplest way around this: inject more information than just energy.

## Evolutionary information

* Use similar proteins (homologs) from databases

* All have been through millions of year of selection by "reality"

* Multiple alignment: align similar regions of the sequences
<figure><img src="image_52.png" /></figure>

Simple integration of information

* Force amino acid choice (constraint) at conserved positions.
Boltzman distribution connects probability and cost/energy

$$P(X) \propto e^{-w(X)}$$
Boltzman distribution connects probability and cost/energy

$$P(X) \propto e^{-w(X)}$$

From CFN to probabilities and back

* After $e^{-x}$ transform, a CFN defines a probability distribution (MRF)
<figure><img src="image_53.png" /></figure>

Boltzman distribution connects probability and cost/energy

$$P(X) \propto e^{-W(X)}$$

From CFN to probabilities and back

* After $e^{-x}$ transform, a CFN defines a probability distribution (MRF)

* Which can be learned from data using maximum penalized likelihood¹,⁶,¹⁰
<figure><img src="image_54.png" /></figure>

Boltzman distribution connects probability and cost/energy

$$P(X) \propto e^{-W(X)}$$

From CFN to probabilities and back

* After $e^{-x}$ transform, a CFN defines a probability distribution (MRF)

* Which can be learned from data using maximum penalized likelihood¹,⁶,¹⁰

* And transformed back into a CFN with $a - \log(x)$ transform
* We start from a complete pairwise CFN with unknown cost functions
* We start from a complete pairwise CFN with unknown cost functions

* We have a total of $d^2 \cdot \frac{n(n-1)}{2}$ parameters to learn
  $w_{ij}(\cdot, \cdot)$
* We start from a complete pairwise CFN with unknown cost functions

* We have a total of $d^2 \cdot \frac{n(n-1)}{2}$ parameters to learn $w_{ij}(\cdot, \cdot)$

* Let $\ell(D|w_{ij})$ be the log-probability of data D given the $w_{ij}$
* We start from a complete pairwise CFN with unknown cost functions

* We have a total of $d^2 \cdot \frac{n(n-1)}{2}$ parameters to learn $w_{ij}(\cdot, \cdot)$

* Let $\ell(D|w_{ij})$ be the log-probability of data D given the $w_{ij}$

Maximize $\ell(D|w_{ij}) - \lambda \cdot ||w_{ij}||$ concave
* We start from a complete pairwise CFN with unknown cost functions

* We have a total of $d^2 \cdot \frac{n(n-1)}{2}$ parameters to learn $w_{ij}(\cdot, \cdot)$

* Let $\ell(D|w_{ij})$ be the log-probability of data D given the $w_{ij}$

Maximize $\ell(D|w_{ij}) - \lambda \cdot ||w_{ij}||$ concave

Efficient L2 norm based implementation available¹⁰

* Uses conjugate gradient optimization

* fast C or very fast CUDA implementation

* n variables, d values, s samples: $O(d^2n^2 + dns)$ space.
* We start from a complete pairwise CFN with unknown cost functions

* We have a total of $d^2 \cdot \frac{n(n-1)}{2}$ parameters to learn $w_{ij}(\cdot, \cdot)$

* Let $\ell(D|w_{ij})$ be the log-probability of data D given the $w_{ij}$

Maximize $\ell(D|w_{ij}) - \lambda \cdot ||w_{ij}||$ concave

Efficient L2 norm based implementation available¹⁰

* Uses conjugate gradient optimization

* fast C or very fast CUDA implementation

* n variables, d values, s samples: $O(d^2n^2 + dns)$ space.

600 variables, domain size 21

80, 000, 000 parameters, estimated in minutes
A counter-productive insulation of fields

* Symbolic (gradient-free) AI already reached super-human performances
A counter-productive insulation of fields

* Symbolic (gradient-free) AI already reached super-human performances

* Numerical (differentiable) AI: you certainly know! (Alpha Go/Zero)
A counter-productive insulation of fields

* Symbolic (gradient-free) AI already reached super-human performances

* Numerical (differentiable) AI: you certainly know! (Alpha Go/Zero)

* But reasoning/planning with Deep Nets? Not at this point.
A counter-productive insulation of fields

* Symbolic (gradient-free) AI already reached super-human performances

* Numerical (differentiable) AI: you certainly know! (Alpha Go/Zero)

* But reasoning/planning with Deep Nets? Not at this point.

* It's now possible to connect them and build hybrid AIs that reason and learn
A counter-productive insulation of fields

* Symbolic (gradient-free) Al already reached super-human performances

* Numerical (differentiable) Al: you certainly know! (Alpha Go/Zero)

* But reasoning/planning with Deep Nets? Not at this point.

* It's now possible to connect them and build hybrid Als that reason and learn

* Graphical models look like a good place to start
<figure><img src="image_55.png" /></figure>

Al/toulbar2

S. de Givry (INRA)

G. Katsirelos (INRA)

M. Zytnicki (PhD, INRA)

D. Allouche (INRA)

H. Nguyen (PhD, INRA)

M. Cooper (IRIT, Toulouse)

J. Larrosa (UPC, Spain)

F. Heras (UPC, Spain)

M. Sanchez (Spain)

E. Rollon (UPC, Spain)

P. Meseguer (CSIC, Spain)

G. Verfaillie (ONERA, ret)

JH. Lee (CU, Hong Kong)

C. Bessiere (LIMM, Montpellier)

JP. Métivier (GREYC, Caen)

S. Loudni (GREYC, Caen)

M. Fontaine (GREYC, Caen)

Protein Design

A. Voet (KU Leuven)

D. Simoncini (INSA, Toulouse)

S. Barbe (INSA, Toulouse)

S. Traoré (PhD, CEA)

C. Viricel (PhD)

PyRosetta (U. John Hopkins)

OSPREY (Duke U.)
[1] Sivaraman Balakrishnan et al. "Learning generative models for protein fold families". In: Proteins: Structure, Function, and Bioinformatics 79.4 (2010), pp. 1061-1078.

[2] Martin C Cooper et al. "Soft arc consistency revisited". In: Artificial Intelligence 174.7 (2010), pp. 449-478.

[3] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.

[4] Oliver Kullmann. "The Science of Brute Force". In: Communications of the ACM (2017).

[5] Nina Narodytska et al. "Verifying properties of binarized deep neural networks". In: Proc. of AAAI'18. 2018.

[6] Youngsuk Park et al. "Learning the Network Structure of Heterogeneous Data via Pairwise Exponential Markov Random Fields". In: Artificial Intelligence and Statistics. 2017. pp. 1302-1310.

[7] Niles A Pierce and Erik Winfree. "Protein design is NP-hard". In: Protein Eng. 15.10 (Oct. 2002), pp. 779-82. ISSN: 0269-2139. URL: http://www.ncbi.nlm.nih.gov/pubmed/12468711.

[8] Daniela Röthlisberger et al. "Kemp elimination catalysts by computational enzyme design". In: Nature 453.7192 (2008), p. 190.

[9] T. Schiex, H. Fargier, and G. Verfaillie. "Valued Constraint Satisfaction Problems: hard and easy problems". In: Proc. of the 14th IJCAI. Montréal, Canada, Aug. 1995, pp. 631-637.

[10] Stefan Seemayer, Markus Gruber, and Johannes Söding. "CCMpred—fast and precise prediction of protein residue-residue contacts from correlated mutations". In: Bioinformatics 30.21 (2014), pp. 3128-3130.

[11] David Simoncini et al. "Guaranteed Discrete Energy Optimization on Large Protein Design Problems". In: Journal of Chemical Theory and Computation 11.12 (2015), pp. 5980-5989. DOI: 10.1021/acs.jctc.5b00594.
[12] Gilles Simonin et al. "Scheduling scientific experiments for comet exploration". In: Constraints 20.1 (2015), pp. 77-99.

[13] Arnout RD Voet et al. "Computational design of a self-assembling symmetrical β-propeller protein". In: Proceedings of the National Academy of Sciences 111.42 (2014), pp. 15102-15107.