Yuquan Lin

2papers

2 Papers

33.7DMMar 27
On merge-models

Hector Buffière, Yuquan Lin, Jaroslav Nešet{ř}il et al.

Tree-ordered weakly sparse models have recently emerged as a robust framework for representing structures in an ``almost sparse'' way, while allowing the structure to be reconstructed through a simple first-order interpretation. A prominent example is given by twin-models, which are bounded twin-width tree-ordered weakly sparse representations of structures with bounded twin-width derived from contraction sequences. In this paper, we develop this perspective further. First, we show that twin-models can be chosen such that they preserve linear clique-width or clique-width up to a constant factor. Then, we introduce \emph{merge-models}, a natural analog of twin-models for merge-width. Merge-models represent binary relational structures by tree-ordered weakly sparse structures. The original structures can then be recovered by a fixed first-order interpretation. A merge-model can be constructed from a merge sequence. Then, its radius-$r$ merge-width will be, up to a constant factor, bounded by the radius-$r$ width of the merge sequence from which it is derived. Finally, we show that twin-models arise naturally as special cases of merge-models, and that binary structures with bounded twin-width are exactly those having a loopless merge-model with bounded radius-$r_0$ merge-width (for some sufficiently large constant $r_0$).

CHEM-PHAug 9, 2021
ChemiRise: a data-driven retrosynthesis engine

Xiangyan Sun, Ke Liu, Yuquan Lin et al.

We have developed an end-to-end, retrosynthesis system, named ChemiRise, that can propose complete retrosynthesis routes for organic compounds rapidly and reliably. The system was trained on a processed patent database of over 3 million organic reactions. Experimental reactions were atom-mapped, clustered, and extracted into reaction templates. We then trained a graph convolutional neural network-based one-step reaction proposer using template embeddings and developed a guiding algorithm on the directed acyclic graph (DAG) of chemical compounds to find the best candidate to explore. The atom-mapping algorithm and the one-step reaction proposer were benchmarked against previous studies and showed better results. The final product was demonstrated by retrosynthesis routes reviewed and rated by human experts, showing satisfying functionality and a potential productivity boost in real-life use cases.