Discrete Differential Geometry and the Structural Study of Protein Complexes

Show more

1. Introduction

Proteins are called the workhorse molecules of life, playing a crucial role in essentially every activity of living organisms. A protein molecule is made from one or more long chains of amino acids, which normally folds into a well-defined three-dimensional structure. It is the precise shape of the folded structure that determines the function of proteins in a cell.

Most cellular processes are not carried out by random collisions between freely diffusing proteins. Proteins usually interact with other proteins and assemble into complexes to carry out their function [1] [2] [3] . It is therefore crucial to understand and control the formation of protein complexes for understanding biological activity in the cell. In particular, structural characterization of the components of complexes, such as shape complementarity at protein- protein interfaces, is the key to understanding the function of proteins.

In the last two decade, huge number of protein structures is experimentally determined via high-throughput structural genomics pipelines. However experimental determination of their functions is lagged far behind the pace due to the labor-intensive and time-consuming nature of the process. Urgently needed are improved computational approaches to function prediction of the proteins with known structure [4] .

It is however extremely difficult to describe the shape of proteins without visual inspection on a three-dimensional display. The fundamental question is how to describe the geometry of such a highly complicated shape as proteins.

In most of previous studies, the surface of proteins is described using concepts developed in computational geometry and topology, such as the Voronoi diagram, the Delaunay simplices, and the alpha shape representation [5] [6] [7] . As for protein complexes, the topological arrangement of their subunits is usually represented as a graph [8] [9] .

The Hamiltonian cycle problem on a regular triangular mesh: a) A region in a regular triangular lattice. b) A Hamiltonian cycle through the region.

An extended version of the Hamiltonian cycle problem on a regular triangular mesh: de nove design of complexes of closed trajectories of triangles. Shown are all the three sets of closed trajectories of triangles which cover the specified region. In this case, the region has no Hamiltonian cycle.

In this paper, we propose a novel mathematical toy model which is intended for the structural study of protein complexes. While physics and mathematics have been inspired each other in their long relationship, the relationship between biology and mathematics is still to come. In our case, it is the relation between real protein complexes and the new mathematical toy model. That is, it is critical to justify why such new toy models are indeed relevant and practically useful.

To justify the usefulness of mathematical tools in biology, I’d like to mention the case of the Estrada index introduced by Ernesto Estrada [10] in 2000. The Estrada index was originally proposed as a molecular structure descriptor, and the protein structure has been investigated by using the Estrada index and the normalized Laplacian Estrada index [11] extensively in mathematics in the past decade. The Estrada indices have also found a range of applications in chemistry and complex networks. These days, a dynamic version of the Estrada indices are proposed [12] to study large-scale time-evolving networks which arise naturally in a variety of areas from peer-to-peer telecommunication to online human social behavior to neuroscience.

As for other mathematical approaches to protein structure analysis, most of them are application of known mathematical techniques to the structural study of proteins, such as, distance geometry [13] , the knot theory [13] , and persistent homology [14] . Differential geometric techniques are also applied to the analysis of the backbone structure of proteins [15] .

In our model, instead of open chains of amino acids, we consider closed trajectories of n-simplices using the discrete differential geometry of n-simplices ( $n=2,3,\cdots $ ) [16] [17] . Then, interaction of open chains of amino acids (i.e., proteins) is mimicked with “recombination”, such as fusion and fission, of closed chains of n-simplices. The advantage of our model lies in the correspondence between the shape of a complex of closed trajectories of n-simplices and (a projection image of) the intersection of a pair of $n+1$ -dimensional cones.

Using the mathematical toy model, we will consider the problem of designing protein complexes from scratch (de novo design of protein complexes [18] [19] [20] ). That is, we will consider the problem of finding a set of closed trajectories of n-simplex that forms a specified n-dimensional shape: de nove design of complexes of closed trajectories of n-simplices. For simplicity, we consider the case of $n=2$ only.

2. Problem

The problem we consider here is an extended version of the Hamiltonian cycle problem on a regular triangular mesh. A Hamiltonian cycle of triangles (i.e., 2- simplices) is a closed trajectory through a given triangular mesh which visits each triangle exactly once, where the trajectory passes triangles through a com- mon edge. As shown in Figure 1(a), meshes are given as a region in a two-di- mensional regular triangular lattice. In this case, a Hamiltonian cycle is obtained as shown in Figure 1(b).

To study the formation of a complex of closed trajectory of triangles, we consider not only a single but also multiple closed trajectories of triangles to cover the given region. In the case of Figure 2, two closed trajectories are required.

In what follows, we will propose a novel method for finding all the sets of closed trajectories which cover a given region of triangles.

3. Differential Structure on the Mesh

To define a differential structure on a regular triangular mesh, we stack unit cubes diagonally in the three-dimensional Euclidean space ${E}^{3}$ (Figure 3(a)).

By piling up unit cubes orderly in the direction of $\left(-\mathrm{1,}-\mathrm{1,}-1\right)$ in ${E}^{3}$ , a “mountain range-like shape object” consisting of multiple triangular cones is obtained as shown in the upper part of Figure 3(c). If we draw a thick straight

(a) (b)

Figure 1. The Hamiltonian cycle problem on a regular triangular mesh. (a) A region in a regular triangular lattice; (b) A Hamiltonian cycle through the region.

line diagonally on the three upper faces of each unit cube, we will obtain a “drawing” on the slope of the mountain range-like shape object (Figure 3(a) and Figure 3(d)). It is the drawing which specifies a flow of “slant” triangles (along the thick polygonal lines) on the slope.

Then, we define a flow of “flat” triangles on a plane which is perpendicular to the direction of $\left(\mathrm{1,1,1}\right)$ in ${E}^{3}$ by projecting the flow of “slant” triangles on the plane (the lower part of Figure 3(c))). In the case of Figure 3(c), we obtain a closed trajectory of flat triangles of length 30 and others. In this section we give the precise definition of the differential structure on a regular triangular mesh.

For space saving purposes, we use monomial in indeterminates ${x}_{0}\mathrm{,}{x}_{1}$ and ${x}_{2}$ to represent the coordinate of points in the three-dimensional Euclidean space. For example, point $p=\left(l,m,n\right)\in {\mathbb{Z}}^{3}$ is identified with monomial ${x}_{0}^{l}{x}_{1}^{m}{x}_{2}^{n}$ , where $\mathbb{Z}$ denotes the set of all integers. Then, points $\left(l+k\mathrm{,}m\mathrm{,}n\right)$ , $\left(l\mathrm{,}m+k\mathrm{,}n\right)$ and $\left(l\mathrm{,}m\mathrm{,}n+k\right)$ are represented by monomials $p{x}_{0}^{k}$ , $p{x}_{1}^{k}$ and $p{x}_{2}^{k}$ respectively. (Note that ${x}_{i}{x}_{j}={x}_{j}{x}_{i}$ for all pairs of i and j.)

3.1. Triangle Tiles

Shown in the upper part of Figure 3(a) is a unit cube with a thick straight line drawn diagonally on each of the upper three faces, which is located at the origin

(a) (b) (c)

Figure 2. An extended version of the Hamiltonian cycle problem on a regular triangular mesh: de nove design of complexes of closed trajectories of triangles. Shown are all the three sets of closed trajectories of triangles which cover the speciﬁed region. In this case, the region has no Hamiltonian cycle.

(a) (b) (c) (d)

Figure 3. Differential structure on a regular triangular mesh. (a) A unit cube and its projection on a plane perpendicular to the direction of $\left(\mathrm{1,1,1}\right)$ in ${E}^{3}$ ; (b) The pro- jection of “slant triangles” onto a “flat triangle”; (c) A “mountain range-like shape object” obtained by piling up unit cubes orderly along the diagonal direction, whose peaks are ${P}_{0}=\left(1,0,0\right)$ , ${P}_{1}=\left(0,0,1\right)$ , ${P}_{2}=\left(-2,2,1\right)$ , ${P}_{3}=\left(0,3,0\right)$ and ${P}_{4}=\left(2,2,-1\right)$ ; (d) A “drawing” on the slope of the mountain range-like shape object of (c).

O of a three-dimensional Cartesian coordinate system defined by three axes ${\phi}_{0}$ , ${\phi}_{1}$ and ${\phi}_{2}$ . Let ${P}_{a}=1$ , ${P}_{b}={x}_{0}$ , ${P}_{c}={x}_{0}{x}_{1}$ , and ${P}_{d}={x}_{1}\in {\mathbb{Z}}^{3}$ . Then, the upper face ${P}_{a}{P}_{b}{P}_{c}{P}_{d}$ on the ${p}_{0}{p}_{1}$ -plane is divided into two “slant triangles”, ${P}_{a}{P}_{b}{P}_{c}$ and ${P}_{a}{P}_{d}{P}_{c}$ , by the line segment ${P}_{a}{P}_{c}$ . The other upper faces are also divided into two “slant triangles” similarly.

Shown in the lower part of Figure 3(a) is the projected image of the unit cube on a plane which is perpendicular to the direction of $\left(\mathrm{1,1,1}\right)$ in ${E}^{3}$ . The unit cube at O is projected onto a hexagon, which is divided into six “flat triangles” by the image of the three thick line segments on the cube.

The schematic drawing of Figure 3(b) shows the projection of slant triangles onto a flat triangle. Using the projection, we will define a discrete differential structure on the set of flat triangles, i.e., a regular triangular mesh.

Let $Sy{m}_{3}$ be the symmetric group on a finite set of three symbols. For $a\in {\mathbb{Z}}^{3}$ and $\rho \in Sy{m}_{3}$ , let $a\left[{x}_{\rho \mathrm{(}\left(0\right)}{x}_{\rho \left(1\right)}\right]$ denote the convex hull of three points $a$ , $a{x}_{\rho \left(0\right)}$ and $a{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\in {\mathbb{Z}}^{3}$ , i.e.,

$\begin{array}{l}a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]:=\{{a}^{{\lambda}_{0}}{\left(a{x}_{\rho \left(0\right)}\right)}^{{\lambda}_{1}}{\left(a{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right)}^{{\lambda}_{2}}|{\lambda}_{0},{\lambda}_{1},{\lambda}_{2}\in \mathbb{R},\underset{}{{{\displaystyle}}_{}}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\underset{}{{{\displaystyle}}_{}}{\lambda}_{0},{\lambda}_{1},{\lambda}_{2}\ge 0,{\lambda}_{0}+{\lambda}_{1}+{\lambda}_{2}=1\}\subset {\mathbb{R}}^{3},\end{array}$

where $\mathbb{R}$ denotes the set of all real numbers.

For example, the “slant triangle” ${P}_{a}{P}_{d}{P}_{c}$ defined above is denoted by $\left[{x}_{1}{x}_{0}\right]=a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]$ , where $a={x}_{0}^{0}{x}_{1}^{0}{x}_{2}^{0}=1$ and $\rho =\left(0,1\right)$ .

Definition 3.1 We define the set ${S}_{2}$ of all slant (triangle) tiles by

${S}_{2}\mathrm{:}=\left\{a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\mathrm{|}a\in {\mathbb{Z}}^{3}\mathrm{,}\rho \in Sy{m}_{3}\right\}\mathrm{.}$

The set ${B}_{2}$ of all flat (triangle) tiles is defined as the quotient of ${S}_{2}$ by “shift operator” $\sigma $ , i.e.,

${B}_{2}:={S}_{2}/\sigma ,$

where $\sigma \left(a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\right)\mathrm{:}=a{x}_{\rho \left(0\right)}\left[{x}_{\rho \left(1\right)}{x}_{\rho \left(2\right)}\right]$ .

We identify ${B}_{2}$ with the projection image of “slant triangles” on a plane perpendicular to vector $\left(\mathrm{1,1,1}\right)$ mentioned above. Then, the schematic drawing of Figure 3(b) shows the equivalence class of a slant tile $s\in {S}_{2}$ and the corresponding flat tile $smod\sigma \in {B}_{2}$ .

3.2. Tangent Space at a Flat Triangle Tile

A tangent bundle-like local structure $T{B}_{2}$ is defined on ${B}_{2}$ by

Definition 3.2 $T{B}_{2}\to {B}_{2}\mathrm{,}\pi $

$\{\begin{array}{l}T{B}_{2}\mathrm{:}={S}_{2}/{\sigma}^{3}\mathrm{,}\hfill \\ \pi \mathrm{:}T{B}_{2}\to {B}_{2}\mathrm{,}\pi \left(smod{\sigma}^{3}\right)=smod\sigma \mathrm{.}\hfill \end{array}$

Let $s\in {S}_{2}$ . Then, we obtain

${\pi}^{-1}\left(smod\sigma \right)=\left\{smod{\sigma}^{3}\mathrm{,}\sigma \left(s\right)mod{\sigma}^{3}\mathrm{,}{\sigma}^{2}\left(s\right)mod{\sigma}^{3}\right\}\mathrm{.}$

Definition 3.3 (Tangent space) For $s\in {S}_{2}$ , we call ${\pi}^{-1}\left(smod\sigma \right)$ the tangent space of ${B}_{2}$ at $smod\sigma $ .

Definition 3.4 For $s=a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\in {S}_{2}$ , the gradient $Ds$ of $s$ is defined by

$Ds:={x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\left(={x}_{\rho \left(1\right)}{x}_{\rho \left(0\right)}\right).$

Then, we can identify $T{B}_{2}$ with

${B}_{2}\times \left\{{x}_{0}{x}_{1}\mathrm{,}{x}_{1}{x}_{2}\mathrm{,}{x}_{0}{x}_{2}\right\}$

via the one-to-one correspondence

$smod{\sigma}^{3}~\left(smod\sigma \mathrm{,}Ds\right)\mathrm{.}$

Note that the monomial $Ds$ of $s\in {S}_{2}$ corresponds to the direction of the thick line on the “slant triangle” $s$ which is described in subsection 3.1 above (Figure 3).

3.3. Vector Field on B_{2}

Having defined a tangent-bundle like structure $\left(T{M}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ on a set of triangles, now we consider the inverse of the projection map $\pi $ .

Definition 3.5 A section $\gamma $ of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ is a map ${B}_{2}\to T{B}_{2}$ such that

$\pi \left(\gamma \left(t\right)\right)=t\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{all}\text{\hspace{0.17em}}t\in {B}_{2}\mathrm{.}$

For a section $\gamma $ of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ , the value of $\gamma $ on $t\in {B}_{2}$ is given by

$\gamma \left(t\right)=s\mathrm{mod}{\sigma}^{3}\in T{B}_{2}$

for some $s=a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\in {S}_{2}$ . Let ${s}_{D}$ and ${s}_{U}$ be two adjacent slant tiles of $s$ in ${S}_{2}$ defined by

$\{\begin{array}{l}{s}_{D}\mathrm{:}=a{x}_{\rho \left(0\right)}\left[{x}_{\rho \mathrm{(1)}}{x}_{\rho \left(0\right)}\right]\in {S}_{2}\mathrm{,}\hfill \\ {s}_{U}\mathrm{:}=a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(2\right)}\right]\in {S}_{2}\mathrm{.}\hfill \end{array}$

(a) (b) (c) (d)

Figure 4. Local trajectory. (a) The local trajectory specified by $s=\left[{x}_{1}{x}_{0}\right]\in {S}_{2}$ . ${s}_{D}={x}_{1}\left[{x}_{0}{x}_{1}\right]$ and ${s}_{U}=\left[{x}_{1}{x}_{2}\right]$ ; (b) The smoothness condition on a section $\gamma $ . Colored gray is $\gamma \left(\left[{x}_{1}{x}_{0}\right]mod\sigma \right)$ and colored white is $\gamma \left(\left[{x}_{1}{x}_{2}\right]mod\sigma \right)$ . Shown above are the gradient of the white tile. The gradient of the gray tile is ${x}_{0}{x}_{1}$ ; (c) Smooth sections of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ on a hexagonal region composed of six flat tiles; (d) Sections of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ which dose not satisfy the smoothness condition. The corresponding sin- gular flat tiles are colored gray in the lower part.

Then, the set of three slant tiles, $\left\{{s}_{D}\mathrm{,}s\mathrm{,}{s}_{U}\right\}$ , makes up a “continuous mountain path” along the thick polygonal line (i.e., along the gradient $Ds$ ) at $s$ in ${S}_{2}$ (Figure 4(a)). By projecting these slant tiles on ${B}_{2}$ , we obtain a trajectory of flat tiles of length three at $smod\sigma $ .

To consider the “smoothness” of the section $\gamma $ , we firstly define a local trajectory passing through $t\in {B}_{2}$ as follows.

Definition 3.6 Let $s\in {S}_{2}$ . The local trajectory specified by $s$ is the set

$\left\{{s}_{D}mod\sigma \mathrm{,}smod\sigma \mathrm{,}{s}_{U}mod\sigma \right\}\subset {B}_{2}\mathrm{,}$

of three consecutive flat tiles passing though $smod\sigma $ .

Let $\gamma $ be a section on ${B}_{2}$ . Then, $\gamma \left(t\right)$ ( $t\in {B}_{2}$ ) can assume one of the three values of the corresponding tangent space ${\pi}^{-1}\left(t\right)$ . For example, $\gamma \left({s}_{U}mod\sigma \right)$ can assume one of the three values of

${\pi}^{-1}\left({s}_{U}mod\sigma \right)=\left\{{x}_{0}^{-1}\left[{x}_{0}{x}_{1}\right]mod{\sigma}^{3}\mathrm{,}\left[{x}_{1}{x}_{2}\right]mod{\sigma}^{3}\mathrm{,}{x}_{1}\left[{x}_{2}{x}_{0}\right]mod{\sigma}^{3}\right\}\mathrm{,}$

where $s=\left[{x}_{1}{x}_{0}\right]\in {S}_{2}$ and ${s}_{U}=\left[{x}_{1}{x}_{2}\right]$ .

However some of the slant tiles are not connected smoothly to $\gamma \left(smod\sigma \right)$ in $T{B}_{2}$ . In this case,

${x}_{1}\left[{x}_{2}{x}_{0}\right]mod{\sigma}^{3}~\left({s}_{U}mod\sigma \mathrm{,}{x}_{0}{x}_{2}\right)$

is not connected smoothly to $\gamma \left(s\mathrm{mod}\sigma \right)=s\mathrm{mod}{\sigma}^{3}$ as shown in Figure 4(b).

To obtain a “smooth” trajectory, we will impose a condition on sections of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ .

Definition 3.7 (Smoothness condition) Let $\gamma $ be a section of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ and $t\in {B}_{2}$ . Let $\gamma \left(t\right)=s\mathrm{mod}{\sigma}^{3}$ , where $s=a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\in {S}_{2}$ . The smoothness condition on $\gamma $ at $t$ is defined by

$\{\begin{array}{l}D\left(\gamma \left({s}_{U}\mathrm{mod}\sigma \right)\right)={x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{x}_{\rho \left(0\right)}{x}_{\rho \left(2\right)},\hfill \\ D\left(\gamma \left({s}_{D}\mathrm{mod}\sigma \right)\right)={x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{or}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{x}_{\rho \left(1\right)}{x}_{\rho \left(2\right)}.\hfill \end{array}$

In what follows, we will only consider the sections of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ which satisfies the smoothness condition at every flat tiles of ${B}_{2}$ .

Remark ${x}_{\rho \left(0\right)}$ corresponds to (the direction of) the contact edge between $s$ and ${s}_{U}$ . ${x}_{\rho \left(1\right)}$ corresponds to (the direction of) the contact edge between $s$ and ${s}_{D}$ .

Definition 3.8 (Vector field) A vector filed on ${B}_{2}$ is a section of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ which satisfies the smoothness condition at every flat tiles of ${B}_{2}$ .

Shown in Figure 4(c) are all the six types of “local” smooth sections of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ on a hexagonal region composed of six flat tiles of ${B}_{2}$ . By patching these “local” sections together, we will obtain a “global” section of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ .

Note that some of the “global” sections do not satisfy the smoothness condition as shown in Figure 4(d). The singular flat tile of a section $\gamma $ of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ is the flat tile where $\gamma $ dose not satisfy the smoothness condition. A singular flat tile is assigned either no gradient (i.e., without thick edge), two gradients (i.e., two thick edges), or three gradients.

Let $\mu =\left\{t\left[i\right]|i\in I\right\}\subset {B}_{2}$ be a trajectory of a vector field V, where I is a subset of the set $\mathbb{N}$ of natural numbers. Then, we can define the second derivative of the trajectory as follows.

Definition 3.9 The second derivative ${D}^{2}V\left(t\left[i\right]\right)$ of V along $\mu $ is a binary-valued (U or D) function defined by

${D}^{2}V\left(t\left[i+1\right]\right)\mathrm{:}=(\begin{array}{ll}{D}^{2}V\left(t\left[i\right]\right)\mathrm{,}\hfill & \text{if}\text{\hspace{0.17em}}DV\left(t\left[i+1\right]\right)=DV\left(t\left[i\right]\right)\hfill \\ -{D}^{2}V\left(t\left[i\right]\right)\mathrm{,}\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{otherwise}\hfill \end{array}$

where $-D:=U$ and $-U:=D$ .

In [16] , the conformation of a protein backbone structure is encoded into a 16-valued sequence using the second derivative of trajectories of tetrahedrons (i.e., 3-simplices).

3.4. Vector Fields Induced by Tangent Cones

In the beginning of this section, we constructed a “mountain range-like shape object” by piling up unit cubes diagonally. (Using the terminology defined above, it is a section of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ .)

Unit cubes are piled up to form a union of triangular cones, which can be identified by its top vertexes. For example, the object shown in the upper part of Figure 3(c) is identified by five peaks ${P}_{0}$ , ${P}_{1}$ , ${P}_{2}$ , ${P}_{3}$ , and ${P}_{4}$ .

Definition 3.10 For $A\subset {\mathbb{Z}}^{3}$ , a tangent cone $ConeA\subset {\mathbb{Z}}^{3}$ is defined by

$ConeA\mathrm{:}=\left\{p{x}_{0}^{{l}_{0}}{x}_{1}^{{l}_{1}}{x}_{2}^{{l}_{2}}|p\in A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{l}_{0}\mathrm{,}{l}_{1}\mathrm{,}{l}_{2}\ge 0\right\}\mathrm{.}$

We denote the set of all the “top vertexes” of $ConeA$ by $p\left(ConeA\right)$ .

Then, the mountain range-like shape object of Figure 3(c) is given by

$Cone\left\{{x}_{0}\mathrm{,}{x}_{2}\mathrm{,}{x}_{0}^{-2}{x}_{1}^{2}{x}_{2}\mathrm{,}{x}_{1}^{3}\mathrm{,}{x}_{0}^{2}{x}_{1}^{2}{x}_{2}^{-1}\right\}\mathrm{.}$

For a tangent cone c, let $dc$ be the set of all the slant tiles on the surfaces of c, i.e.,

$dc:=\left\{a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\in {S}_{2}|a,a{x}_{\rho \left(0\right)}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}a{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\text{\hspace{0.17em}}\text{are}\text{\hspace{0.17em}}\text{on}\text{\hspace{0.17em}}\text{the}\text{\hspace{0.17em}}\text{surfaces}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}c\right\}.$

For $z\in {\mathbb{Z}}^{3}$ and $c=ConeA$ ( $A\subset {\mathbb{Z}}^{3}$ ), set

${l}_{c}\left(z\right):=\underset{p\in c}{\mathrm{max}}\left\{\mathrm{min}\left\{{l}_{0},{l}_{1},{l}_{2}\right\}|z={x}_{0}^{{l}_{0}}{x}_{1}^{{l}_{1}}{x}_{2}^{{l}_{2}}p\right\}.$

Then, $dc$ is given as follows.

Lemma 3.11 For $c=ConeA$ ( $A\subset {\mathbb{Z}}^{3}$ ),

$dc=\left\{a\left[{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right]\in {S}_{2}|{l}_{c}\left(a\right)={l}_{c}\left(a{x}_{\rho \left(0\right)}\right)={l}_{c}\left(a{x}_{\rho \left(0\right)}{x}_{\rho \left(1\right)}\right)=0\right\}$

Proof. Let $z\mathrm{,}p\in {\mathbb{Z}}^{3}$ . Then, $z={x}_{0}^{{l}_{0}}{x}_{1}^{{l}_{1}}{x}_{2}^{{l}_{2}}p$ for some $\left({l}_{0}\mathrm{,}{l}_{1}\mathrm{,}{l}_{2}\right)\in {\mathbb{Z}}^{3}$ . $\left({l}_{0}\mathrm{,}{l}_{1}\mathrm{,}{l}_{2}\right)$ is the coordinate of z with respect to “origin” p. In particular,

$\begin{array}{l}z\in Cone\left\{p\right\}\iff {l}_{0},{l}_{1},{l}_{2}\ge 0,\\ z\in d\left(Cone\left\{p\right\}\right)\iff \mathrm{min}\left\{{l}_{0},{l}_{1},{l}_{2}\right\}=0.\end{array}$

The result follows immediately.

The surfaces of a tangent cone c induce a vector field of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ as follows.

Definition 3.12 For $c=ConeA$ ( $A\subset {\mathbb{Z}}^{3}$ ), a vector field ${V}_{c}$ induced by c is defined by

${V}_{c}\left(t\right):=s\mathrm{mod}{\sigma}^{3}\text{\hspace{1em}}\left(t\in {B}_{2}\right),$

where $s\in dc$ such that $t=s\mathrm{mod}\sigma $ . The value ${V}_{c}\left(t\right)$ is uniquely determined at every flat tile of ${B}_{2}$ .

For example, in Figure 3(c), the thick polygonal lines on the surfaces of the tangent cone $Cone\left\{{x}_{0}\mathrm{,}{x}_{2}\mathrm{,}{x}_{0}^{-2}{x}_{1}^{2}{x}_{2}\mathrm{,}{x}_{1}^{3}\mathrm{,}{x}_{0}^{2}{x}_{1}^{2}{x}_{2}^{-1}\right\}$ shows the vector field induced by the tangent cone.

Note that all the smooth sections shown in Figure 4(c) are induced by a tangent cone as indicated in the figure.

Proposition 3.13 For any vector field V, there exists a tangent cone c such that $V={V}_{c}$ .

Proof. Let V be a vector filed on ${B}_{2}$ and let $E=\left\{{U}_{i}|i\in \mathbb{N}\right\}$ be a decomposition of ${B}_{2}$ into hexagonal regions of six flat tiles:

${B}_{2}={\displaystyle \cup \left\{{U}_{i}|i\in \mathbb{N}\right\}}\mathrm{.}$

For ${U}_{i}\in E$ , we let ${V|}_{{U}_{i}}$ denote the restriction of V on the hexagon ${U}_{i}$ .

Because of the smoothness condition, V is locally induced by a tangent cone as shown in Figure 3(c). That is, there exists a tangent cone ${c}_{i}$ for each ${U}_{i}\in E$ such that ${V|}_{{U}_{i}}={{V}_{{c}_{i}}|}_{{U}_{i}}$ , i.e.,

$V\left(t\right)={V}_{{c}_{i}}\left(t\right)\text{\hspace{1em}}\text{for}\text{\hspace{0.17em}}\forall \text{\hspace{0.17em}}t\in {U}_{i}\mathrm{.}$

Moreover, by considering all combinations, we can assume

${V|}_{{U}_{j}\cup {U}_{k}}={{V}_{{c}_{j}\cup {c}_{k}}|}_{{U}_{j}\cup {U}_{k}}$ (1)

for any pair of adjacent hexagons ${U}_{j}$ and ${U}_{k}$ , where ${c}_{j}\cup {c}_{k}$ denote the union of two tangent cones ${c}_{j}$ and ${c}_{k}$ , i.e., $Cone\text{\hspace{0.17em}}p\left({c}_{j}\right)\cup p\left({c}_{k}\right)$ .

Suppose that $V\ne {V}_{c}$ for $c={\displaystyle {\cup}_{i\in \mathbb{N}}{c}_{i}}$ . Then,

$\exists {U}_{a}\in E\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}{{V}_{{c}_{a}}|}_{{U}_{a}}\ne {{V}_{c}|}_{{U}_{a}}\mathrm{.}$

In particular, $\exists b\in \mathbb{N}$ such that

$\exists {t}_{0}\in {U}_{a}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}{V}_{c}\left({t}_{0}\right)={V}_{{c}_{b}}\left({t}_{0}\right)\mathrm{.}$

In other words, tangent cone ${c}_{a}$ is (partially) covered by tangent cone ${c}_{b}$ on ${U}_{a}$ .

Then, there exists a circular loop $\Theta $ of hexagons of $E$ around ${U}_{b}$ such that

$\exists {U}_{e}\in \Theta \text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}{{V}_{{c}_{e}}|}_{{U}_{e}}\ne {{V}_{{c}_{e}\cup {c}_{b}}|}_{{U}_{e}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{{V}_{{c}_{i}}|}_{{U}_{i}}={{V}_{{c}_{i}\cup {c}_{b}}|}_{{U}_{i}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\forall {U}_{i}\in \Omega \mathrm{,}$

where $\Omega $ is the set of all the hexagons of $E$ contained in the circular region surrounded by $\Theta $ . Because of the shape of the tangent cones, $\exists {U}_{f}\in \Omega $ such that ${U}_{f}$ is adjacent to ${U}_{e}$ and ${c}_{e}$ is (partially) covered by ${c}_{f}$ on ${U}_{e}$ , i.e.,

$\exists {t}_{1}\in {U}_{e}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}{V}_{c}\left({t}_{1}\right)={V}_{{c}_{f}}\left({t}_{1}\right)\ne {V}_{{c}_{e}}\left({t}_{1}\right)\mathrm{.}$

In particular,

${{V}_{{c}_{e}}|}_{{U}_{e}}\ne {{V}_{{c}_{e}\cup {c}_{f}}|}_{{U}_{e}}\mathrm{,}$

which is in contradiction to Equation (1).

4. The Boundary of a Closed Trajectory

Now let’s go back to our problem described in section 2. Using the terminology given in section 3, the problem is stated as follows.

Problem 4.1. (De nove design of complexes of closed trajectories of triangles) Given a region in ${B}_{2}$ , find all the vector fields on ${B}_{2}$ which give a decomposition of the region into closed trajectories.

If there exists such a vector field, we can describe the boundary of the region using a pair of three-dimensional cones as explained in this section.

The cones are defined in another lattice which is associated with ${\mathbb{Z}}^{3}$ . Recall that the three-dimensional lattice ${\mathbb{Z}}^{3}$ is generated by ${x}_{0}$ , ${x}_{1}$ and ${x}_{2}$ . The associated lattice is defined as follows.

Definition 4.2. The conjugate lattice ${\mathbb{L}}_{3}$ is the lattice which is generated by ${x}_{0}{x}_{1}$ , ${x}_{1}{x}_{2}$ and ${x}_{0}{x}_{2}$ .

Note that the gradient of a slant tile corresponds to one of the three coordinate axes of the conjugate lattice ${\mathbb{L}}^{3}$ . In particular, a trajectory of slant tiles corresponds to a zig-zag walk (with gaps) on the grid of ${\mathbb{L}}^{3}$ .

Two types of cones are defined in ${\mathbb{L}}_{3}$ :

Definition 4.3. For $A\subset {\mathbb{L}}_{3}$ , a cotangent cone $Con{e}^{\mathrm{*}}A\subset {\mathbb{L}}^{3}$ is defined by

$Con{e}^{\mathrm{*}}A\mathrm{:}=\left\{p{\left({x}_{1}{x}_{2}\right)}^{{l}_{0}}{\left({x}_{0}{x}_{2}\right)}^{{l}_{1}}{\left({x}_{0}{x}_{1}\right)}^{{l}_{2}}|p\in A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{l}_{0}\mathrm{,}{l}_{1}\mathrm{,}{l}_{2}\ge 0\right\}\mathrm{.}$

For $A\subset {\mathbb{L}}_{3}$ , a cotangent roof $Roo{f}^{\mathrm{*}}A\subset {\mathbb{L}}^{3}$ is defined by

$Roo{f}^{*}A:=\left\{p\in {\mathbb{L}}^{3}|\exists N>0\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}p{\left({x}_{1}{x}_{2}\right)}^{N},p{\left({x}_{0}{x}_{2}\right)}^{N},p{\left({x}_{0}{x}_{1}\right)}^{N}\in Con{e}^{*}A\right\}.$

In other words, $Roo{f}^{\mathrm{*}}A$ is obtained by putting as many unit cubes as possible on $Con{e}^{\mathrm{*}}A$ .

For example, shown in Figure 5(c) is

(a) (b) (c)

Figure 5. Cotangent roofs associated with a closed trajectory on ${B}_{2}$ . (a) The boundary of the closed trajectory of Figure 3(c); (b) The cotangent roof of the region, where ${Q}_{0}={x}_{2}^{-1}$ , ${Q}_{1}={x}_{0}^{-1}$ and ${Q}_{2}={x}_{0}^{-2}{x}_{1}$ ; (c) The inverted cotangent roof of the region, where ${Q}_{3}={x}_{0}^{3}{x}_{1}^{3}{x}_{2}$ and ${Q}_{4}={x}_{0}^{2}{x}_{1}^{4}{x}_{2}^{3}$ .

$Roo{f}^{*}\left\{{x}_{0},{x}_{2},{x}_{0}^{-2}{x}_{1}^{2}{x}_{2},{x}_{1}^{3},{x}_{0}^{2}{x}_{1}^{2}{x}_{2}^{-1}\right\}\left(=Con{e}^{*}\left\{{x}_{2}^{-1},{x}_{0}^{-1},{x}_{0}^{-2}{x}_{1}\right\}\right).$

Inverted cones are also defined similarly:

Definition 4.4. For $A\subset {\mathbb{L}}_{3}$ , an inverted cotangent cone $ICon{e}^{\mathrm{*}}A\subset {\mathbb{L}}^{3}$ is defined by

$ICon{e}^{\mathrm{*}}A\mathrm{:}=\left\{p{\left({x}_{1}{x}_{2}\right)}^{{l}_{0}}{\left({x}_{0}{x}_{2}\right)}^{{l}_{1}}{\left({x}_{0}{x}_{1}\right)}^{{l}_{2}}|p\in A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{l}_{0}\mathrm{,}{l}_{1}\mathrm{,}{l}_{2}\le 0\right\}\mathrm{.}$

For $A\subset {\mathbb{L}}_{3}$ , an inverted cotangent roof $IRoo{f}^{\mathrm{*}}A\subset {\mathbb{L}}^{3}$ is defined by

$IRoo{f}^{\mathrm{*}}A\mathrm{:}=\left\{p\in {\mathbb{L}}^{3}|\exists N<0\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}p{\left({x}_{1}{x}_{2}\right)}^{N}\mathrm{,}p{\left({x}_{0}{x}_{2}\right)}^{N}\mathrm{,}p{\left({x}_{0}{x}_{1}\right)}^{N}\in ICon{e}^{\mathrm{*}}A\right\}\mathrm{.}$

For example, shown in Figure 5(c) is

$IRoo{f}^{\mathrm{*}}\left\{{x}_{0}\mathrm{,}{x}_{2}\mathrm{,}{x}_{0}^{-2}{x}_{1}^{2}{x}_{2}\mathrm{,}{x}_{1}^{3}\mathrm{,}{x}_{0}^{2}{x}_{1}^{2}{x}_{2}^{-1}\right\}\left(=ICon{e}^{\mathrm{*}}\left\{{x}_{0}^{3}{x}_{1}^{3}{x}_{2}\mathrm{,}{x}_{0}^{2}{x}_{1}^{4}{x}_{2}^{3}\right\}\right)\mathrm{.}$

Then, the boundary of a closed trajectory of a vector field on ${B}_{2}$ can be described using a pair of a cotangent roof and an inverted cotangent roof as shown below.

Let w be a cotangent cone. We denote by $\partial \left(w\right)$ the set of all the lattice points of ${\mathbb{L}}^{3}$ which resides on the surface of the cone w. $\partial \left(w\right)$ is called the boundary lattice points of w. The boundary lattice points of an inverted cotangent cone is also defined in the same manner.

Proposition 4.5. Let ${V}_{c}$ be a vector field of $\left(T{B}_{2}\mathrm{,}{B}_{2}\mathrm{,}\pi \right)$ induced by a tangent cone c whose top vertexes $p\left(c\right)$ are in ${\mathbb{L}}_{3}$ . Let $\mu =\left\{t\left[i\right]|i\in I\right\}$ ( $I\subset \mathbb{N}$ ) be a closed trajectory of ${V}_{c}$ . Let ${R}_{\mu}$ be the region swept by the trajectory $\mu $ .

Then, there exist a cotangent cone w and an inverted cotangent cone $iv$ such that the boundary of ${R}_{\mu}$ is uniquely specified by the intersection of $\partial \left(w\right)$ and $\partial \left(iv\right)$ .

The pair $\left(w\mathrm{,}iv\right)$ is called a boundary pair (of the region ${R}_{\mu}$ ) and the specified region is denoted by ${R}_{\left(w\mathrm{,}iv\right)}$ , i.e. ${R}_{\left(w,iv\right)}={R}_{\mu}$ .

Proof. Let $\Lambda =\left\{s\left[i\right]|i\in I\right\}$ be a subset of ${S}_{2}$ such that

${V}_{c}\left(t\left[i\right]\right)=s\left[i\right]mod{\sigma}^{3}$ ( $i\in I$ ).

Because of the smoothness condition, we may assume slant tiles of $\Lambda $ are connected “smoothly” in ${S}_{2}$ without any gap. Let A be the set of all vertexes of the slant tiles of $\Lambda $ . Define cones w and iv by

$\{\begin{array}{l}w=Roo{f}^{*}A,\\ iv=IRoo{f}^{*}A.\end{array}$

Then, the boundary of ${R}_{\mu}$ is obtained by connecting the points of $\pi \left(\partial \left(w\right)\cap \partial \left(iv\right)\right)$ on ${B}_{2}$ , where $\pi $ denotes the projection of the lattice points of ${\mathbb{Z}}^{3}$ on the corresponding vertexes of flat tiles of ${B}_{2}$ .

Remark $Roo{f}^{\mathrm{*}}p\left(c\right)$ is not defined if $p\left(c\right)\notin {\mathbb{L}}^{3}$ .

For example, in the case of the closed trajectory given in Figure 3(d), the boundary of ${R}_{\mu}$ is uniquely specified by

$\{\begin{array}{l}w=Con{e}^{*}\left\{{Q}_{0},{Q}_{1},{Q}_{2}\right\},\\ iv=ICon{e}^{*}\left\{{Q}_{3},{Q}_{4}\right\}\end{array}$

as shown in Figure 5.

Corollary 4.6. Let R be a region in ${B}_{2}$ . Then, R has a closed-trajectory decomposition if and only if there exists a pair of a cotangent cone w and an inverted cotangent cone iv such that $R={R}_{\left(w,iv\right)}$ . The pair $\left(w,iv\right)$ is also called a boundary pair (of R).

Proof. ( $\to $ ) Let $\left\{{\mu}_{i}\mathrm{|}i\in I\right\}$ ( $I\subset \mathbb{N}$ ) be a closed-trajectory decomposition of R and let $\left\{\left({w}_{i}\mathrm{,}i{v}_{i}\right)\mathrm{|}i\in I\right\}$ be their boundary pairs. Set

$\{\begin{array}{l}w={\displaystyle {\cup}_{i\in I}{w}_{i}},\\ iv={\displaystyle {\cup}_{i\in I}i{v}_{i}}.\end{array}$

Then, $R={\displaystyle {\cup}_{i\in I}{R}_{{\mu}_{i}}}={\displaystyle {\cup}_{i\in I}{R}_{\left({w}_{i},i{v}_{i}\right)}}$ .

( $\leftarrow $ ) A closed-trajectory decomposition of R is induced by $Cone\text{\hspace{0.17em}}\partial \left(w\right)\cap \partial \left(iv\right)$ .

Remark Let $\mathbb{T}$ be the set of all tangent cones. Let $\u2102$ be the set of all cotangent cones. Let $\mathbb{L}$ be the set of all the regions in ${B}_{2}$ which are defined by boundary pairs. Then, an $\mathbb{L}$ -valued function is defined on $\mathbb{T}\times \u2102$ by $\langle ConeA\mathrm{,}Con{e}^{\mathrm{*}}B\rangle $ := “the region in ${B}_{2}$ which is specified by the intersection of $ConeA$ and $Con{e}^{\mathrm{*}}B$ “. In particular,

$\langle Cone\text{\hspace{0.17em}}\partial \left(w\right)\cap \partial \left(iv\right)\mathrm{,}w\rangle ={R}_{\left(w\mathrm{,}iv\right)}\mathrm{,}$

for a boundary pair $\left(w,iv\right)$ .

5. Extended Hamiltonian Cycle Problem on B_{2}

5.1. Problem

By Corollary 4.6, we can paraphrase Problem 4.1 as follows.

Problem 5.1. (De nove design of complexes of closed trajectories of triangles) Given a boundary pair $\left(w,iv\right)$ , find all the tangent cones which induce such a vector field that gives a decomposition of the region ${R}_{\left(w,iv\right)}$ into closed trajectories (Figure 6).

(a) (b)

Figure 6. The extended Hamiltonian cycle problem on ${B}_{2}$ (See also Figure 1). (a) A pair of a cotangent cone and an inverted cotangent cone which specifies the boundary of a region: $Roo{f}^{\mathrm{*}}A$ and $IRoo{f}^{\mathrm{*}}B$ , where $A\mathrm{,}B\subset {\mathbb{L}}^{3}$ ; (b) A tangent cone which induces such a vector field whose trajectories don’t traverse the specified boundary: $Cone\text{\hspace{0.17em}}C$ , where $C=\partial \left(Roo{f}^{*}A\right)\cap \partial \left(IRoo{f}^{*}B\right)$ .

One of the solutions to the problem is obtained immediately, i.e., $Cone\text{\hspace{0.17em}}\partial \left(w\right)\cap \partial \left(iv\right)$ (Figure 6(b)). In this section, we consider how to find all solutions to the problem.

5.2. Closed-Trajectory Decomposition

Definition 5.2. For $A\subset {\mathbb{Z}}_{3}$ , a tangent roof $RoofA\subset {\mathbb{Z}}^{3}$ is defined by

$Roof\text{\hspace{0.17em}}A:=\left\{p\in {\mathbb{Z}}^{3}|\exists N>0\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}p{\left({x}_{0}\right)}^{N},p{\left({x}_{1}\right)}^{N},p{\left({x}_{2}\right)}^{N}\in Cone\text{\hspace{0.17em}}A\right\}.$ In other words, $RoofA$ is obtained by putting as many unit cubes as possible on $ConeA$ .

Definition 5.3. For $A\subset {\mathbb{Z}}_{3}$ , a (tangent) ceiling $CeilA\subset {\mathbb{Z}}^{3}$ is defined by

$Ceil\text{\hspace{0.17em}}A:=Cone\text{\hspace{0.17em}}C,$

where

$C={\displaystyle \cup \left\{B|Roo{f}^{*}B=Roo{f}^{*}A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}IRoo{f}^{*}B=IRoo{f}^{*}A\right\}}\subset {\mathbb{Z}}^{3}.$

For $A\subset {\mathbb{Z}}_{3}$ , a (tangent) floor $FloorA\subset {\mathbb{Z}}^{3}$ is defined by

$Floor\text{\hspace{0.17em}}A:=Cone\text{\hspace{0.17em}}C,$

where

$C={\displaystyle \cap \left\{B|Roo{f}^{*}B=Roo{f}^{*}A\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}IRoo{f}^{*}B=IRoo{f}^{*}A\right\}}\subset {\mathbb{Z}}^{3}.$

It follows immediately that

$\{\begin{array}{l}Floor\text{\hspace{0.17em}}A\subset Ceil\text{\hspace{0.17em}}A,\\ Roof\text{\hspace{0.17em}}p\left(Floor\text{\hspace{0.17em}}A\right)=Roof\text{\hspace{0.17em}}A,\\ Roof\text{\hspace{0.17em}}p\left(Ceil\text{\hspace{0.17em}}A\right)=Roof\text{\hspace{0.17em}}A,\end{array}$

where $p\left(c\right)$ denotes the set of all the “top vertexes” of a cone c.

For a boundary pair $\left(w,iv\right)$ , let ${W}_{\left(w,iv\right)}$ be the set of all the tangent cones c such that

$Floor\text{\hspace{0.17em}}C\subset c\subset Ceil\text{\hspace{0.17em}}C,$

where $C=\partial \left(w\right)\cap \partial \left(iv\right)$ .

Now all solutions to Problem 5.1 are obtained as follows:

Proposition 5.4. ${W}_{\left(w,iv\right)}$ induces all decompositions of ${R}_{\left(w,iv\right)}$ into closed trajectories.

Proof. ( $\to $ ) Let $VF$ be the set of all the vector fields whose trajectories don’t traverse the boundary of ${R}_{\left(w,iv\right)}$ . Then,

${V}_{c}\in VF\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{any}\text{\hspace{0.17em}}c\in {W}_{\left(w,iv\right)}$

because $\left(Roo{f}^{\mathrm{*}}p\left(c\right)\mathrm{,}IRoo{f}^{\mathrm{*}}p\left(c\right)\right)=\left(w\mathrm{,}iv\right)$ . In particular, ${V}_{c}$ induces a decompositions of ${R}_{\left(w,iv\right)}$ into closed trajectories.

( $\leftarrow $ ) Given a decomposition of ${R}_{\left(w,iv\right)}$ into closed trajectories. Then, it can be extended to a vector field V on ${B}_{2}$ . For example, a flow of triangles on ${B}_{2}\backslash {R}_{\left(w,iv\right)}$ is induced by

${V}_{Cone\text{\hspace{0.17em}}\partial \left(w\right)\cap \partial \left(iv\right)}\mathrm{.}$

Then, $\exists $ a tangent cone c such that $V={V}_{c}$ by proposition 3.13. Then

$\left(Roo{f}^{*}p\left(c\right),IRoo{f}^{*}p\left(c\right)\right)=\left(w,iv\right)$

because trajectories of ${V}_{c}$ don’t traverse the boundary of ${R}_{\left(w,iv\right)}$ .

For example, Figure 7 shows all solutions to the problem for the boundary pair of Figure 5.

5.3. Fusion and Fission of Closed Trajectories

For a vector field V on ${B}_{2}$ and a region R of ${B}_{2}$ , let $Dec\left(V\mathrm{,}R\right)$ be the set of all closed trajectories of V in R. $Dec\left(V\mathrm{,}R\right)$ gives a closed-trajectory decomposition of R if it exists. The number of the closed trajectories of $Dec\left(V\mathrm{,}R\right)$ is denoted by $\mathrm{\#}Dec\left(V\mathrm{,}R\right)$ .

For a boundary pair $\left(w\mathrm{,}iv\right)$ , let $c0$ and $c1$ ( $c0\ne c1$ ) be two tangent cones of ${W}_{\left(w,iv\right)}$ . Then, vector fields ${V}_{c0}$ and ${V}_{c1}$ induce two different decompositions of ${R}_{\left(w,iv\right)}$ : $Dec\left({V}_{c0}\mathrm{,}{R}_{\left(w,iv\right)}\right)$ and $Dec\left({V}_{c1}\mathrm{,}{R}_{\left(w,iv\right)}\right)$ . The correspondence

$Dec\left({V}_{c0}\mathrm{,}{R}_{\left(w,iv\right)}\right)\leftrightarrow Dec\left({V}_{c1}\mathrm{,}{R}_{\left(w,iv\right)}\right)$

gives a “recombination” of closed trajectories from one to the other. In particular, it gives a “fusion” and “fission” of closed trajectories on ${R}_{\left(w,iv\right)}$ if

$\mathrm{\#}Dec\left({V}_{c0}\mathrm{,}{R}_{\left(w,iv\right)}\right)>1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\mathrm{\#}Dec\left({V}_{c1}\mathrm{,}{R}_{\left(w,iv\right)}\right)=1.$

In the case of Figure 7, the region ${R}_{\left(w,iv\right)}$ has three decompositions but no Hamiltonian cycle:

$\{\begin{array}{l}\#Dec\left({V}_{Cone\text{\hspace{0.17em}}C},{R}_{\left(w,iv\right)}\right)=2\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(\text{a})\\ \#Dec\left({V}_{Cone\text{\hspace{0.17em}}C\cup \left\{{x}_{1}^{2}\right\}},{R}_{\left(w,iv\right)}\right)=2\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}(\text{b})\\ \#Dec\left({V}_{Cone\text{\hspace{0.17em}}C\cup \left\{{x}_{1}\right\}},{R}_{\left(w,iv\right)}\right)=2\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}\text{\hspace{0.17em}}(\text{c})\end{array}$

Moreover, it is not difficult to show the following proposition (in the case of closed trajectories of triangles):

(a) (b) (c)

Figure 7. All solutions to the extended Hamiltonian cycle problem for a boundary pair $\left(w\mathrm{,}iv\right)$ , where $\partial \left(w\right)\cap \partial \left(iv\right)=\left\{{x}_{0},{x}_{2},{x}_{0}^{-2}{x}_{1}^{2}{x}_{2},{x}_{1}^{3},{x}_{0}^{2}{x}_{1}^{2}{x}_{2}^{-1},{x}_{0}{x}_{1}^{3}{x}_{2}^{-1}\right\}$ (See also Figure 2). Set $C=\partial \left(w\right)\cap \partial \left(iv\right)$ . (a) The vector field induced by $Floor\text{\hspace{0.17em}}C$ ; (b) The vector field induce by $Cone\text{\hspace{0.17em}}C\cup \left\{{x}_{1}^{2}\right\}$ which is obtained by putting a cube (with top vertex ${x}_{1}^{2}$ ) on $Floor\text{\hspace{0.17em}}C$ ; (c) The vector field induced by $Ceil\text{\hspace{0.17em}}C=Cone\text{\hspace{0.17em}}C\cup \left\{{x}_{1}\right\}$ , which is obtained by putting a cube (with top vertex ${x}_{1}$ ) on the vector field of (b).

Proposition 5.5. When a closed trajectory is merged with a closed trajectory of length 6 (which occupies a hexagonal region), they don’t fuse together to form a single closed trajectory.

In other words, closed trajectories always split when they interact with a hexagon.

See Tabel 1 for the distribution of the length of closed trajectories of n-sim- plices ( $n=2,3,4$ ).

The distribution of the length of closed trajectories of n-simplices ( $n=2,3,4$ ). Two closed trajectories are identified if and only if their sequences of the second derivative coincide with each other by rotational shift, inversion, or reversion.

6. Conclusions

We have considered an extended version of a two-dimensional Hamiltonian cycle problem in a three-dimensional setting, where the boundary of a two-di- mensional region is uniquely specified by a pair of three-dimensional cones, i.e., a boundary pair. Using the discrete differential geometry of triangles, all decompositions of the region into closed trajectories of triangles are obtained immediately from the intersection of the boundary pair.

In the structural study of protein complexes, it is essential to characterize surface features such as bumps (convexity) and dents (concavity) of protein molecules. However mathematical surface characterization has not produced any satisfactory results so far, where the surface of protein molecules is usually studied in a three-dimensional setting.

This paper proposes a novel mathematical approach to the structural study of protein complexes, i.e., an approach from a four-dimensional setting, where the surface of protein molecules is to be described by a pair of four-dimensional cones (with multiple top vertexes) as in the case of complexes of closed trajectories of triangles.

In our approach, protein molecules are to be represented as closed trajectories of tetrahedrons, where shape complementarity is expressed inherently. In particular, we could define fusion and fission of molecules (i.e., closed trajectories) naturally.

As a future research subject, we are considering whether there exist any (algebraic) equations a given boundary pair satisfies. If there exists a set of such equations that specifies the given boundary pair, it is possible to represent the shape

Table 1. The distribution of the length of closed trajectories of n-simplices ( $n=2,3,4$ ). Two closed trajectories are identified if and only if their sequences of the second derivative coincide with each other by rotational shift, inversion, or reversion.

of a protein molecule as a solution for a system of equations. In particular, we would obtain another protein molecule of the same function if a given set of equations has more than one solution.

References

[1] Alberts, B. (1998) The Cell as a Collection of Protein Machines: Preparing the Next Generation of Molecular Biologists. Cell, 92, 291-294.

https://doi.org/10.1016/S0092-8674(00)80922-8

[2] Ponstingl, H., Kabir, T., Gorse, D. and Thornton, J.M. (2005) Morphological Aspects of Oligomeric Protein Structures. Progress in Biophysics and Molecular Biology, 89, 9-35.

[3] Pereira-Leal, J.B., Levy, E.D. and Teichmann, S.A. (2006) The Origins and Evolution of Functional Modules: Lessons from Protein Complexes. Philosophical Transactions of the Royal Society B: Biological Sciences, 361, 507-517.

https://doi.org/10.1098/rstb.2005.1807

[4] Lee, D., Redfern, O. and Orengo, C. (2007) Predicting Protein Function from Sequence and Structure. Nature Reviews Molecular Cell Biology, 8, 995-1005.

https://doi.org/10.1038/nrm2281

[5] Edelsbrunner, H. (2001) Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge.

https://doi.org/10.1017/CBO9780511530067

[6] Gerstein, M and Richards, F.M. (2001) Protein Geometry: Volumes, Areas, and Distances. In: Rossman, M.G. and Arnold, E., Eds., The International Tables for Crystallography, Vol. F, Chap. 22, Kluwer, Dordrecht, 531-539.

[7] Ban, Y.-E.A., Edelsbrunner, H. and Rudolph, J. (2006) Interface Surfaces for Protein-Protein Complexes. Journal of the ACM, 53, 361-378.

https://doi.org/10.1145/1147954.1147957

[8] Levy, E.D., Pereira-Leal, J.B., Chothia, C. and Teichmann, S.A. (2006) 3D Complex: A Structural Classification of Protein Complexes. PLoS Computational Biology, 2, e155.

https://doi.org/10.1371/journal.pcbi.0020155

[9] Perica, T., Marsh, J.A., Sousa, F.L., Natan, E., Colwell, L.J., Ahnert, S.E. and Teichmann, S.A. (2012) The Emergence of Protein Complexes: Quaternary Structure, Dynamics and Allostery. Biochemical Society Transactions, 40, 475-491.

https://doi.org/10.1042/BST20120056

[10] Estrada, E. (2000) Characterization of 3D Molecular Structure. Chemical Physics Letters, 319, 713-718.

[11] Li, J., Guo, J. and Shiu, W.C. (2014) The Normalized Laplacian Estrada Index of a Graph. Filomat, 28, 365-371.

https://doi.org/10.2298/FIL1402365L

[12] Shang, Y. (2015) Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs. PLoS ONE, 10, e0123426.

https://doi.org/10.1371/journal.pone.0123426

[13] Taylor, W.R. and Aszodi, A. (2004) Protein Geometry, Classification, Topology and Symmetry: A Computational Analysis of Structure. Taylor & Francis, UK.

[14] Edelsbrunner, H., Letscher, D. and Zomorodian, A. (2002) Topological Persistence and Simplification. Discrete & Computational Geometry, 28, 511-533.

https://doi.org/10.1007/s00454-002-2885-2

[15] Goriely, A., Hausrath, A. and Neukirch, S. (2008) The Differential Geometry of Proteins and Its Applications to Structure Determination. Biophysical Reviews and Letters, 3, 77-101.

https://doi.org/10.1142/S1793048008000629

[16] Morikawa, N. (2014) Discrete Differential Geometry of n-Simplices and Protein Structure Analysis. Applied Mathematics, 5, 2458-2463.

https://doi.org/10.4236/am.2014.516237

[17] Morikawa, N. (2016) Discrete Differential Geometry of Triangles and Escher-Style Trick Art. Open Journal of Discrete Mathematics, 6, 161-166.

https://doi.org/10.4236/ojdm.2016.63013

[18] Woolfson, D.N., Bartlett, G.J., Burton, A.J., Heal, J.W., Niitsu, A., Thomson, A.R. and Wood, C.W. (2015) De Novo Protein Design: How Do We Expand into the Universe of Possible Protein Structures? Current Opinion in Structural Biology, 33, 16-26.

[19] Huang, P.-S., Boyken, S.E. and Baker, D. (2016) The Coming of Age of de Novo Protein Design. Nature, 537, 320-327.

https://doi.org/10.1038/nature19946

[20] Norn, C.H. and Andre, I. (2016) Computational Design of Protein Self-Assembly. Current Opinion in Structural Biology, 39, 39-45.