Construction of the cSAS and the eSAS
To start the construction, we need some quantities for representing different com- ponents of the SAS. First, an intersection point will be represented by its coordinate in R3 and an identifier. Second, to represent a circular arc, we use its starting and ending intersection points (resp. the identifiers), its radius, center and radian as well as an identifier. Finally, to represent a spherical patch, we use the SAS-sphere on which it lies on and the identifiers of all circular arcs forming its boundary. Then, we propose to construct the SAS in five basic steps as below:
1) Compute the set of all intersection points fx1; ; xm1 g, denoted by I.
2) Calculate each SAS circular arc or circle lm associated with some Si and Sj . For each SAS circular arc or circle, we record the information, including the center, the radius, the radian, the corresponding two SAS spheres, the identifiers of the starting and ending intersection points. Notice that each circular arc connects two intersection points.
3) Construct all loops on each SAS sphere Si, which also form the boundaries of SAS spherical patches on Si. Notice that each loop is composed of circular arcs, or a complete circle. We start from a circular arc on Si, find another arc connecting this arc, add it into the loop, and repeat this until we finally obtain a complete loop. The k-th loop on the i-th SAS sphere is denoted by Li k.
4) Construct all spherical patches on each SAS sphere Si. Since the boundary of a spherical patch on Si is composed by one or several loops on Si, we can use the identifiers of these loops to represent a spherical patch. Denote by Pi k the k-th spherical patch on Si. The difficulty lies on determining whether two loops on Si belong to the boundary of a common spherical patch or not. This final question will be discussed in the next section.
5) Finally, we should distinguish the cSAS and the eSAS. The cSAS is just the set of all above-constructed SAS spherical patches. To construct the eSAS, we say that two spherical patches Pi k and Pj l are neighbors if they have a common circular arc or circle on their boundaries. Then, we start our construction of the eSAS, by mapping a faraway point p1 onto an SAS spherical patch, which is the initial patch on the eSAS. Then, we add the neighboring spherical patches into the eSAS one by one, to finally obtain the whole eSAS.
Binary tree to construct spherical patches
In the above construction process, there remains a problem of classifying the loops on an SAS-sphere into several parts, such that each part forms the boundary There are six loops on the SAS-sphere fL1;L2;L3;L5;L6;L6g, and three spherical patches with the boundaries formed by two loops in green fL4;L5g, three loops in red fL1;L3;L6g and one loop (circle) in blue fL2g respectively. The tree on the right illustrates the corresponding binary tree whose leaves identify the boundaries of three different spherical patches. of a spherical patch. To do this, we need to determine whether two loops on the SAS-sphere belong to the boundary of a same spherical patch or not. Note that two ifferent loops won’t cross each other but can have common vertices. We propose to construct a binary tree whose leaves are the different spherical patches. Given a loop L on a fixed SAS-sphere Si, L divides the sphere into two open parts and it is composed of circular arcs formed by the intersection of Si and other SAS-spheres. We call the open part of Si which is not hidden by those other SAS- spheres as the interior of L, denoted by L◦, while the other open part as the exterior of L, denoted by Lc. We say that another loop L′ on Si is inside L if L′ 2 L◦, where L◦ = L [ L◦ is the closed hull of L◦ on Si. Notice that each loop L being part of the boundary of a spherical patch contains all the other loops that belong to the boundary of the same patch. By testing if a loop L′ on Si is inside the loop L, we can classify all loops on Si into two parts: the loops inside L (including L itself) and the remaining loops outside L. We do this division repeatedly until each loop is tested which results in a binary tree.To better understand this process, let’s see the example of Figure 15. On an SAS- sphere Si, there are six loops fL1;L2;L3;L5;L6;L6g forming three spherical patches fP1; P2; P3g with green, red and blue boundaries. The leaves of the binary tree in Figure 15 represent the boundary of the three spherical patches. To construct the tree, consider all loops fL1;L2;L3;L5;L6;L6g and test with L1, to divide into the set of loops inside L1 (fL1;L2;L3;L6g) and the set of the remaining loops outside L (fL4;L5g). Then, we test with L2, to find that L2 is inside itself, while fL1;L3;L6g are outside, which implies that L2 itself forms the boundary of a spherical patch. Afterwards, we find that fL1;L6g are both inside L3 by testing with L3 and that fL1;L3g are inside L6 by testing with L6. This implies that fL1;L3;L6g form the boundary of the second spherical patch, as these three loops are inside each other. Finally, we test respectively with L4 and L5 to find that they are inside each other and they form the boundary of the last spherical patch.
Construction of molecular surfaces
This section will focus on the construction of molecular surfaces by calculating different components of them. We only consider the SAS and the SES since the construction of the VdW-surface is the same as the SAS. Furthermore, we assume that any SAS-ball is not included in another one (otherwise, the inner SAS-ball can be ignored).
Data structures of the SAS
We first need to compute an intersection matrix in which the i-th row records the neighboring SAS-spheres intersected with the i-th SAS-sphere. To retrieve all neighboring SAS-spheres, we can use a data structure called a binary spatial division tree proposed by Barnes and Hut with the average complexity O(logM) [12, 102] where M is the number of atoms. In practice, the maximum number of intersected SAS-spheres for a given SAS-sphere is bounded by a constant kmax. As a consequence, the intersection matrix is defined of size M kmax and each row reports the indices of the neighboring spheres. Based on this intersection matrix, we can establish data structures of the components of both the SAS and then the SES.
An intersection point on the SAS can in theory be formed by the intersection of more than three SAS-spheres. This can appear quite often due to symmetries. In this case, the intersection can however be divided into multiple triplets of SAS- spheres for simplicity. Therefore, we assume that any intersection point is formed by the intersection of three SAS-spheres. On each SAS-sphere, we calculate the intersection points formed by the intersection with any two neighboring SAS-spheres. After calculating the intersection points on each SAS-sphere, we obtain the set of all intersection points I. An intersection point has the following data structure:
(x; y; z): coordinate of the point.
(i; j; k): indices of three corresponding SAS-spheres.
Once the mesh of a molecular patch is established, it is easy to refine it uniformly. Indeed, we can bisect each edge of the mesh and map its middle point to the closest point on the patch which can be computed given the data structure of the patch.
Then, each triangle is replaced with four smaller triangles formed by the three vertices of this triangle and three closest points to the middle points of the three edges. As a consequence, the refined mesh consists of these smaller triangles. This process of refinement is quite efficient with the complexity proportional to the number of triangles in the mesh.
In many cases, high-quality meshes of molecular surfaces are required. One way to further improve the meshes generated by the above advancing-front algorithm is to use surface remeshing tools. With a remeshing tool, one can usually set some quality requirements and obtain an output mesh approximating well the input mesh. Figure 10 illustrates the mesh of caffeine using the remeshing tool MMGS developed by Dapogny et al.  as an example. One should notice that in this case, the remeshing can not ensure that all vertices lie exactly on the molecular surfaces anymore but it can keep the initial vertices of the input mesh.
Table of contents :
1 The larger context
2 Implicit solvation models
3 Domain decomposition methods for implicit solvation models
I Molecular Surfaces
1 Mathematical analysis and calculation of molecular surfaces
1.2 Introduction to implicit surfaces
1.3 Implicit molecular surfaces
1.4 Solvent accessible surface
1.5 Solvent excluded surface
1.6 Construction of molecular surfaces
1.7 Numerical results
2 Meshing molecular surfaces based on analytical implicit representa- tion
2.2 Molecular surfaces
2.3 Construction of molecular surfaces
2.4 Molecular inner holes
II Domain Decomposition Method for Implicit Solvation Models
3 Domain Decomposition Method for the Polarizable Continuum Model based on the Solvent Excluded Surface
3.2 Solute-solvent boundary
3.3 Dielectric permittivity function
3.4 Problem formulation and global strategy
3.5 Domain decomposition strategy
3.6 Single-domain solvers
3.7 Numerical results
4 Domain Decomposition Method for the Poisson-Boltzmann Solvation Model
4.2 PB solvation model
4.3 Problem transformation
4.5 Single-domain solvers
4.6 Global linear system
4.7 Numerical results
A Proof of Theorem 1.5.1
B Advancing-front algorithm for a spherical patch
C Appendices in Chapter 3
C.1 Well-posedness of (3.6.7)
C.2 Computation of @ @Y m ℓ and @ @φY m ℓ
C.3 Computation of f(x) in (3.6.6)
D Computation of C1; C2; F0 173