# The Coherent Multi-representation Problem for Protein Structure Determination

Antonio Mucherino, Jung-Hsin Lin

► To cite this version:

Antonio Mucherino, Jung-Hsin Lin. The Coherent Multi-representation Problem for Protein Structure Determination. Lecture Notes in Computer Science 14321, H. Moosaei et al. (Eds.), Sep 2023, Prague, Czech Republic. pp.194-202. [hal-04647132](https://hal-04647132)

HAL Id: hal-04647132

https://inria.hal.science/hal-04647132v1

Submitted on 13 Jul 2024

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Coherent Multi-representation Problem for Protein Structure Determination

A. Mucherino<fnref n="1" />, J-H. Lin<fnref n="2" />

**Abstract.** The Coherent Multi-representation Problem (CMP) was recently introduced and presented as an extension of the well-known Distance Geometry Problem (DGP). In this short contribution, we establish a closer relationship between the CMP and the problem of protein structure determination based on NMR experiments. Moreover, we introduce the concept of “level of coherence” for the several representations involved in the CMP, and provide some details about some ongoing research directions.

## 1 Introduction

Determining the three-dimensional conformation of biological molecules is of extreme importance in structural biology. These conformations can in fact reveal the potential functions that such molecules are in change of performing in living beings [3]. Moreover, they can also disclose additional information on how a given molecule can interact with particular chemical components, hence aiding at the development of new drugs [15]. Several approaches have been proposed in the past years for the determination of protein conformations, and in this work we focus on the one based on new introduced Coherent Multi-representation Problem (CMP) [16] where the data are obtained through experiments of Nuclear Magnetic Resonance (NMR) [2, 20].

Historically, the determination of protein structures with the solution NMR technique relies mainly on the distance restraints, which are mainly derived from the cross peaks in NOESY spectra [9]. It usually requires a large number of distance restraints to obtain highly accurate protein structures, and the useful distance restraints come from the NMR signal from residues far from each other in the amino acid sequences of proteins. However, it is a highly non-trivial task to obtain a large number of distance restraints, due to the overlaps of resonances and peaks, artifacts in spectra and noise, and the missing signals due to the too fast motions of protein domains and loops. Once the collection of the distance restraints of the protein of interest is sufficient, a popular approach of determining protein structures are Simulated Annealing (SA) heuristics with constrained molecular dynamics simulations in the torsional space [10, 21]. A key ingredient in this approach is an efficient algorithm for calculations of first and second derivatives of potential energy in the torsional space [1], which enables torsional angle dynamics (TAD) and its many application. More recently, NMR spectra are also exploited to find some estimations on the feasible values of torsion angles that can be defined on protein backbones [24].

<footnote n="1">¹IRISA, University of Rennes, Rennes, France. Email: antonio.mucherino@irisa.fr</footnote>

<footnote n="2">²RCAS and NBRP, Academia Sinica, Taipei, Taiwan. Email: jhlin@gate.sinica.edu.tw</footnote>
By focusing mainly on the distance information, other approaches have been proposed in the scientific literature in the past years in order to overcome the typical issues related to the use of heuristic methods. Historical examples are the approaches in [4, 5, 11], while more recent efforts can be found for example in the survey [13] and the collection [17].

In the CMP, the main idea is to have different geometric representations for the atoms of the protein (for example, one based on distances, and another rather based on angles), that finally need to be “coherent” when constructing the overall three-dimensional conformation for the protein [16]. The CMP is NP-hard and it generalizes another problem known in the scientific literature as the Distance Geometry Problem (DGP) [13].

In this short contribution, we will make a point on the current ongoing research activities in the context of the CMP for the specific application arising in structural biology. Section 2 will briefly introduce the CMP in the context of the considered biological problem, by pointing out how NMR experiments are actually able to provide the exploited geometrical information. Then, we will discuss in Section 3 our current efforts in adding new and more complex representations to the CMP, while Section 4 some ideas will be presented for an automatic differentiation of the mathematical function in charge of measuring the level of coherence of each representation. Finally, Section 5 will briefly sum up the content of the paper, and conclude.

## 2 The CMP for protein structure determination

Proteins are chains of amino acids. Each of the 20 amino acids that can be involved in the protein synthesis share a common group of atoms which takes part in forming the so-called protein backbone. The atoms contained in the protein backbone are basically hydrogen, carbon and nitrogen atoms. For simplicity in this work, we focus on protein backbones only.

A simple representation for a protein backbone consists in assigning a triplet of Cartesian coordinates to each of its atoms:

$$x: V \to \mathbb{R}^3, \qquad (1)$$

where V is a given set of atoms forming the protein. However, in structural biology, it is more common to employ another alternative representation for the protein backbones, which is based on the torsion angles that we can define for each quadruplet of consecutive atoms:

$$\omega: V \setminus \{v_1, v_2, v_3\} \to [-2\pi, 2\pi), \qquad (2)$$

where the numerical labels assigned to the vertices indicate their “natural order” in the protein, the one that follows the protein sequence and allows us to define a meaningful torsion angle for every quadruplet of consecutive vertices (these angles are generally referred to as *dihedral angles*). The first 3 vertices are not in the domain of $\omega$, and we suppose that their Cartesian coordinates can be fixed, together with the other distances and angles involved in the definition of the torsion angles [14].

The study of the chemical composition of protein backbones can already give us some important information about protein conformations. Indeed, the presence of an
atom in the protein backbone is known in advance, together with the information about
its neighboring atoms through the existence of chemical bonds. In presence of a chem-
ical bond, we can associate a distance to the two bonded atoms, which basically only
depends on the kinds of atoms. Similarly, we can estimate in a rather precise way the
distances between atoms that are chemically bonded to another common atom.

This overall distance information is very useful for protein modeling but it only
gives local information: it gives no clues about the interactions between atoms that are
located in parts of the chain that are separated by several amino acids in the protein
sequence. Information with this global character can be obtained by performing exper-
iments of Nuclear Magnetic Resonance (NMR) [2]. Generally, these experiments focus
on hydrogen atoms and they can detect, by studying the magnetic properties of atomic
nuclei, the close proximity of hydrogen atoms belonging to amino acids largely distant
in the protein sequence. On the basis of this detection mechanism in NMR, it is possi-
ble to assign a distance value to pairs of hydrogen atoms that can be found in different
parts of the protein, providing in this way information about the global geometry of the
protein.

Several computational approaches are based on Euclidean distances only [17], i.e. ge-
ometrical information having a pure distance nature. However, distances are not the only
kind of information that we can use in the context of protein structure determination. In
order to introduce another kind of information, we point out that the NMR experiments
are able to perform the prediction on the distances by studying some electro-magnetic
signals that are related to the *precession* phenomenon of the aforementioned atomic
nuclei in the proteins [20]. It turns out that this very same signal can also be used in
artificial neural networks, such as the ones developed in tools of the TALOS *family*
(TALOS+, TALOS-N) that exploit such raw signals to perform estimations on the typ-
ical torsion angles φ and ψ that we can define on protein backbones [23, 24].

While some attempts of conversions from non-distance to distance information can
be found in the scientific literature [12], it is evident that these conversions cannot al-
ways be performed without losing part of the information. For this reason, the CMP has
been introduced in [16] in order to take into consideration different kinds of geometri-
cal information at once in problems such as the one we are focusing in this paper in the
context of structural biology.

The CMP can be represented by a simple directed graph $G = (V, E)$, where the ver-
tices are atoms and there is an edge between two atoms when a geometrical relationship
between them can be established. Orientations of the edges directly imply an order on
the vertices of $G$. No weights are associated to the edges, nor to the vertices. It is rather
through the specific multi-representation system that numerical values can be associ-
ated to the edges of the graph. In order to exploit the information obtained through
NMR experiments, we can consider that one kind of information is given by the dis-
tance between two atoms, while another kind of information rather connects two atoms
because there exists a torsion angle in the protein backbone having these two atoms at
its two extreme ends.

The possibility to have multiple representations occurs at two different levels in the
CMP. First of all, for every edge of the set E, we can consider more than one represen-
tation for the destination vertex (recall that the edges are directed in G). For example,
for the same pair of vertices, we may have both distance and torsion angle information, hence allowing for the destination vertex to have two different representations. Moreover, the multiplicity of the representations can also be found again at the level of the entire graph, where all these local representations will have to find coherent values for their internal variables for defining a final and global realization $x$ for the graph. For the formal definitions, the reader is referred to [16].

Let $Y$ be the definition domain for the internal variables related to a non-Cartesian representation for a given vertex (e.g. the torsion angle representation, where $Y$ has only one dimension). We refer to a coordinate transformation, capable to convert the coordinates from one system to another, as a triplet $(P, Y, f)$, where $P$ is the set of parameters (e.g. the fixed distances and angles in the quadruplets related to the torsion angles), $Y$ is the coordinate domain, and $f$ is the mapping:

$$f: (p, y) \in P \times Y \rightarrow x \in \mathbb{R}^3, \qquad (3)$$

that performs the transformation from the variables $y \in Y$ to the standard Cartesian coordinates $x \in \mathbb{R}^3$. The definition is given above for dimension 3 but can be trivially extended to any dimensions; we normally suppose that $f$ is differentiable.

We say that a given vertex has *expected Cartesian coordinates* when its (possibly several) representations are all defined, so that the average value over each of its Cartesian coordinates can be computed. When these average values all correspond (for a given tolerance) to the ones obtained through the transformations, we say then that the several representations for the vertex are coherent. The *level of coherence* can be simply computed as the averaged variance among the different Cartesian coordinates obtained through the various representations for the same vertex. The level of coherence can play the role of penalty function in optimization problems attempting to find values for all representation variables that are able to make the system coherent.

## 3 New representations in the multi-representation

The *secondary structure* of a protein is related to some typical local arrangements of the protein chain. There are only two main secondary structures. The $\alpha$-helix is an arrangement of the sequence of consecutive amino acids having the form of a helix where the number of amino acids per turn is fixed by chemical bonds so that the entire structure can only have slight fluctuations. The $\beta$-sheet structure is a little more complex: it is composed by a set of sequences of consecutive amino acids which take the form of a strand (where basically the amino acid appear like being aligned on an almost straight line). Different parts of the protein sequence can have the form of a strand, and then such a set of strands can have different possible ways to arrange themselves in the three-dimensional space in order to form a $\beta$-sheet. Because of the chemical bonds that take place between pairs of strands when generating a $\beta$-sheet structure, we can count combinatorially the various possible organizations in space for these strands.

When information about the protein secondary structures is available, we can consider to integrate it in our CMP instances. In previous works, this kind of information was translated into distance information [18], and subsequently included in the list containing the other available distances. In the context of the CMP, we can rather consider
to have a dedicated kind of representation in the multi-representation system where several atoms are involved, and not only one per time.

From a mathematical point of view, the introduction of representations acting on multiple atoms requires an extension of the codomain of the transformation mappings involved in the change of coordinates (from internal coordinates for a given representation, to the standard Cartesian coordinates):

$$ \hat{f}: (p, y) \in P \times Y \rightarrow \hat{x} \in \mathbb{R}^{3 \times m}, $$

where m is the number of involved atoms. Here atoms are not represented as single entities (as it is the case when using distance or angle information) but they are rather together with other atoms in some local conformations. From a technical point of view, this extension has an important impact on the current implementation in Java of the CMP<fnref n="1" />. In fact, the notification system, which attempts keeping all representation in a coherent state at all times, is currently based on the idea that, as soon as there is a change in one representation, all the others that depend on this one are notified of the change. When one of such notifications will arrive to a representation involving several atoms, the system will have to manage all these atoms, and possibly notify in turn all the other representations regarding these atoms.

An immediate consequence of including new representations based on secondary structures is therefore an expected higher complexity of the implementations. We expect however to strongly reduce the search space related to our CMP instances when these new representations will be taken into consideration.

## 4 Dual numbers and automatic differentiation

Dual numbers remind of complex numbers for the way they are defined, but are essentially different [22]. They are pairs of real numbers $(r, t)$, which we can also write as $r + \varepsilon t$, where it is supposed that $\varepsilon^2 = 0$. This assumption implies the definition of specific arithmetic operations on dual numbers where the component $t$ is able to carry information about derivatives of functions $f(r)$ where $r$ appears as a variable. When replacing a dual number $(r, 1)$ with the real number $r$ in a given mathematical function, in fact, one simple function evaluation in $(r, 1)$ allows us to construct the new dual number $(f(r), f'(r))$, which contains the value of the function in $r$, as well as the value of the function derivative in $r$. We remark that the approach is also valid for trigonometric functions, and can be extended to functions admitting multiple variables.

In our ongoing research, the main idea is to use the properties of dual numbers to perform an automatic differentiation of the transformation functions (see equ. (3)), in order to automatically construct the gradient of the function measuring the level of coherence for the multi-representations. We will give an example below related to the two representations via Cartesian coordinates in equ. (1) and through torsion angles (see equ. (2)). The importance of tools for automatic differentiation comes from the need of using local optimization methods, such as the Spectral Projected Gradient (SPG) [19]

<footnote n="1">¹ https://github.com/mucherino/DistanceGeometry, javaCMP folder.</footnote>
and the Levenberg-Marquardt Algorithm (LMA) [8], both already used in the context of distance geometry in previous publications.

A torsion angle $\omega_i$ corresponds to a quadruplet of Cartesian coordinates for consecutive vertices $v_{i-3}$, $v_{i-2}$, $v_{i-1}$ and $v_i$. Since the very first 3 vertices are supposed to be fixed in the Cartesian space, every torsion angle $\omega_i$ only controls the position of the fourth vertex in each quadruplet of consecutive vertices. The transformation formula that we employ is the one proposed in [7], and it makes use of the three Cartesian coordinates for $v_{i-3}$, $v_{i-2}$ and $v_{i-1}$, as well as of the value of $\omega_i$, to compute the Cartesian coordinates for $v_i$. This is done by defining a local coordinate system having as origin the Cartesian coordinates of $v_{i-1}$. The unit vectors of the defined coordinate system can be organized in matrix form so that to define a $3 \times 3$ matrix to which we refer with the symbol $U_{i-1}$ (our notations are consistent with the original discussion in [7]).

From a given torsion angle $\omega_i$, the Cartesian coordinates $(x_i, y_i, z_i)$ of $v_i$, together with the numerical derivatives $(x'_i, y'_i, z'_i)$, over the three coordinates, of the applied transformation, can be computed as:

$$ \begin{bmatrix} (x_i, x'_i) \\ (y_i, y'_i) \\ (z_i, z'_i) \end{bmatrix} = \begin{bmatrix} x_{i-1} \\ y_{i-1} \\ z_{i-1} \end{bmatrix} + U_{i-1} \begin{bmatrix} -d(i-1, i) \cos \theta_i \\ d(i-1, i) \sin \theta_i \cos (\omega_i, 1) \\ d(i-1, i) \sin \theta_i \sin (\omega_i, 1) \end{bmatrix}, \quad (4) $$

where $\theta_i$ is a constant and corresponds to the vector angle formed by the Cartesian coordinates of $v_{i-3}$, $v_{i-2}$ and $v_{i-1}$. Notice the use of the dual number $(\omega_i, 1)$ as an argument for both sine and cosine functions. Naturally, the calculations need to be performed in dual arithmetic in order to obtain the desired result.

We are aware of the fact that the transformation mapping used above is rather simple, so that the symbolic differentiation may be used instead. If we opt for the use of automatic differentiation through dual arithmetic is because of our wish is to keep our method as general as possible. This will allow us to more easily integrate, for example, the new alternative representations briefly discussed in Section 3. Moreover, it is worth mentioning that, in general, every representation is based on the expected Cartesian coordinates of another, which need to be taken into consideration when differentiating, in particular when the derivatives are to be computed on the variables used in the representation that plays the role of reference. We believe the use of dual numbers will make our implementations more efficient, as well as elegant.

# 5 Conclusions

We have presented the newly introduced CMP in an informal way (as opposite to the formal introduction appeared in [16]) by taking as an example the natural application of the CMP in the context of structural biology. Moreover, we have given some emphasis to the two main research directions that we are currently investigating for the CMP. Firstly, we are studying the possibility of adding new representations in the multi-representation system of the CMP, including some representations where groups of atom are involved at once. We have considered representations where the several atoms take part in the definition of protein secondary structures, but a further extension to “protein blocks” is also possible [6]. Secondly, we are working on automatic tools for the differentiation of
the transformation mappings, and hence for the function in change to compute the level of coherence for the several representations for a given atom. These research lines will be further investigated in the near future, and the corresponding codes (currently under development) will appear on the GitHub repository named "DistanceGeometry".

## Acknowledgments

This work is partially supported by the international PRCI project MULTIBIOSTRUCT, co-funded by the ANR French funding agency (ANR-19-CE45-0019) and the National Science and Technology Council (NSTC) of Taiwan (MoST 109-2923-M-001-004-MY3). Most of the discussions, giving rise to some of the ideas presented in this paper, took indeed place during one of the visits of AM to Academia Sinica.

## References

1. H. Abe, W. Braun, T. Noguti, N. Gō, *Rapid Calculation of First and Second Derivatives of Conformational Energy with Respect to Dihedral Angles for Proteins General Recurrent Equations*, Computers & Chemistry 8(4), 239-247, 1984.

2. F.C.L. Almeida, A.H. Moraes, F. Gomes-Neto, *An Overview on Protein Structure Determination by NMR, Historical and Future Perspectives of the Use of Distance Geometry Methods*. In: [17], 377-412, 2013.

3. I.N. Berezovsky, E. Guarnera, Z. Zheng, *Basic Units of Protein Structure, Folding, and Function*, Progress in Biophysics & Molecular Biology 128, 85-99, 2017.

4. W. Braun, C. Bösch, L.R. Brown, G. Ō Nobuhiro, K. Wüthrich, *Combined Use of Proton-Proton Overhauser Enhancements and a Distance Geometry Algorithm for Determination of Polypeptide Conformations*. Application to Micelle-Bound Glucagon, Biochimica et Biophysica Acta - Protein Structure 667(2), 377-396, 1981.

5. G.M. Crippen, T.F. Havel, *Distance Geometry and Molecular Conformation*, John Wiley & Sons, 1988.

6. A.G. de Brevern, H. Valadié, S. Hazout, C. Etchebest, *Extension of a Local Backbone Description using a Structural Alphabet: a New Approach to the Sequence-Structure Relationship*, Protein Science 11(12), 2871-2886, 2002.

7. D.S. Gonçalves, A. Mucherino, *Discretization Orders and Efficient Computation of Cartesian Coordinates for Distance Geometry*, Optimization Letters 8(7), 2111-2125, 2014.

8. D.S. Gonçalves, A. Mucherino, *A Distance Geometry Procedure using the Levenberg-Marquardt Algorithm and with Applications in Biology but not only*, Lectures Notes in Computer Science 13347, Lecture Notes in Bioinformatics series, Proceedings of the 9th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO22), Gran Canaria, Spain, 142-152, 2022.

9. P. Güntert, L. Buchner, *Combined Automated NOE Assignment and Structure Calculation with CYANA*, Journal of Biomolecular NMR 62, 453-471, 2015.

10. P. Güntert, C. Mumenthaler, K. Wüthrich, *Torsion Angle Dynamics for NMR Structure Calculation with the New Program DYANA*, Journal of Molecular Biology 273(1), 283-298, 1997.

11. T.F. Havel, I.D. Kuntz, G.M. Crippen, *The Theory and Practice of Distance Geometry*, Bulletin of Mathematical Biology 45, 665-720, 1983.

12. S.B. Hengeveld, T. Malliavin, L. Liberti, A. Mucherino, *Collecting Data for Generating Distance Geometry Graphs for Protein Structure Determination*, Proceedings of ROADEF23, Rennes, France, 2 pages, February 2023.
13. L. Liberti, C. Lavor, N. Maculan, A. Mucherino, *Euclidean Distance Geometry and Applications*, SIAM Review **56**(1), 3–69, 2014.

14. T.E. Malliavin, A. Mucherino, M. Nilges, *Distance Geometry in Structural Biology: New Perspectives*. In: [17], Springer, 329–350, 2013.

15. I.S. Moreira, P.A. Fernandes, M.J. Ramos, *Protein–Protein Docking Dealing with the Unknown*, Journal of Computational Chemistry **31**(2), 317–342, 2010.

16. A. Mucherino, *The Coherent Multi-Representation Problem with Applications in Structural Biology*, Lecture Notes in Computer Science **13919**, Lecture Notes in Bioinformatics series, I. Rojas et al. (Eds.), Proceedings of the 10th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO23), Gran Canaria, Spain, 338–346, 2023.

17. A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), *Distance Geometry: Theory, Methods and Applications*, 410 pages, Springer, 2013.

18. A. Mucherino, C. Lavor, T. Malliavin, L. Liberti, M. Nilges, N. Maculan, *Influence of Pruning Devices on the Solution of Molecular Distance Geometry Problems*, Lecture Notes in Computer Science **6630**, P.M. Pardalos and S. Rebennack (Eds.), Proceedings of the 10th International Symposium on Experimental Algorithms (SEA11), Crete, Greece, 206–217, 2011.

19. A. Mucherino, J-H. Lin, D.S. Gonçalves, *A Coarse-Grained Representation for Discretizable Distance Geometry with Interval Data*, Lecture Notes in Computer Science **11465**, Lecture Notes in Bioinformatics series, I. Rojas et al (Eds.), Proceedings of the 7th International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO19), Part I, Granada, Spain, 3–13, 2019.

20. C. Nascimento, *Ressonância Magnética Nuclear* (in Portuguese), Blusher, São Paulo, 120 pages, 2016.

21. M. Nilges, *Calculation of Protein Structures with Ambiguous Distance Restraints. Automated Assignment of Ambiguous NOE Crosspeaks and Disulphide Connectivities*, Journal of Molecular Biology **245**(5), 645–660, 1995.

22. E. Pennestri, R. Stefanelli, *Linear Algebra and Numerical Algorithms using Dual Numbers*, Multibody System Dynamics **18**, 323–344, 2007.

23. Y. Shen, A. Bax, *Protein Structural Information Derived from NMR Chemical Shift with the Neural Network Program TALOS-N*, Methods in Molecular Biology **1260**, 17–32, 2015.

24. Y. Shen, F. Delaglio, G. Cornilescu, A. Bax, *TALOS+: a Hybrid Method for Predicting Protein Backbone Torsion Angles from NMR Chemical Shifts*, Journal of Biomolecular NMR **44**(4), 213–236, 2009.