{'fraction_non_alphanumeric': 0.0403506800044959, 'fraction_numerical': 0.019107564347532878, 'mean_word_length': 4.5522620904836195, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hydropathy Conformational Letter and its Substitution Matrix HP-CLESUM: an Application to Protein Structural Alignment

Motivation: Protein sequence world is discrete as 20 amino acids (AA) while its structure world is continuous, though can be discretized into structural alphabets (SA). In order to reveal the relationship between sequence and structure, it is interesting to consider both AA and SA in a joint space. However, such space has too many parameters, so the reduction of AA is necessary to bring down the parameter numbers. Result: We've developed a simple but effective approach called entropic clustering based on selecting the best mutual information between a given reduction of AAs and SAs. The optimized reduction of AA into two groups leads to hydrophobic and hydrophilic. Combined with our SA, namely conformational letter (CL) of 17 alphabets, we get a joint alphabet called hydropathy conformational letter (hp-CL). A joint substitution matrix with (17*2)*(17*2) indices is derived from FSSP. Moreover, we check the three coding systems, say AA, CL and hp-CL against a large database consisting proteins from family to fold, with their performance on the TopK accuracy of both similar fragment pair (SFP) and the neighbor of aligned fragment pair (AFP). The TopK selection is according to the score calculated by the coding system's substitution matrix. Finally, embedding hp-CL in a pairwise alignment algorithm, say CLeFAPS, to replace the original CL, will get an improvement on the HOMSTRAD benchmark.


I. INTRODUCTION
Proteins fold into specific spatial conformations to perform their biological functions [1] and there are abundant evidences to show their amino acid (AA) sequences determining the structures [2]. The attempt to find the relationship between structure and sequence is a fundamental task in computational biology [4].
Compared to the sequence world which is discrete of 20 AAs, the structure world is continuous, though the local conformational space of a protein backbone fragment is rather limited [5]. The idea of representing the backbone with a string of discrete letters was first observed by Corey and Pauling [6,7] and later refined into the concept of protein secondary structure elements (SSEs). However, segments of a single SSE may vary significantly in their 3D structures, especially for the state coil, which is not a true secondary structure but is a class of conformations that indicate the absence of regular SSEs, say alpha helix or beta strand [23]. Although the SSE can be predicted with high accuracy (≥80%) [3], the description of a protein in terms of its SSEs is not sufficient to capture accurately its 3D geometry [20].
To overcome this limitation, several groups have proposed the idea that representing protein structures as a series of overlapping fragments, each labeled with a symbol, which defines a structural alphabet (SA) for proteins [8][9][10][11][12][13]. Such alphabet can be used to predict local structure [15][16][17], to reconstruct the full-atom representation [18], to identify the structural motifs [19], to classify protein structures [20] and to search against a database [21,22]. We've proposed our SA, namely conformational letter (CL) [14], which is composed of 17 alphabets and each with 4 residues in length. Our SA is focused on the fast pairwise [24], multiple [25] and flexible [26] structure alignment problems, combined with its substitution matrix CLESUM [14].
After we discretized the continuous structure world into SAs, it is the time to consider both AA and SA in a joint space. However, such space is too large for about (20 * 17) 2 parameters when using the current popular SAs. It is necessary to employ the reduction of AAs [27]. Several groups have put forward their reduced AAs either experimentally or computationally. For example, Baker et.al found a five-letter alphabet for 38 out of 40 selected sites of SH3 chain [28]; Wang & Wang [29] introduced the minimal mismatch principle to reduce the alphabet based on Miyazawa-Jernigan's residue-residue statistical potential [30]; Murphy et.al [31] approached the same problem using the BLOSUM matrix [32]. Recently, de Brevern et.al proposed to use their SA, namely Protein Blocks [10] to analyze equivalences between the different kinds of amino acids, then obtained their reduced AAs [33].
Here we present a novel reduction method, called entropic clustering [34]. Briefly, given two discrete distributions A and B, merging a i and a j into one group a i&j will result in a loss of mutual information of A and B. Thus, mutual information I can be naturally chosen as the objective function for optimized clustering. When grouping the 20 AAs into two categories, we've got a result of hydrophobic and hydrophilic, which agrees with HP-model [35] exactly. Then we construct a joint substitution matrix HP-CLESUM with (17 * 2) 2 indices by the similar means as constructing CLESUM.
The following tests are employed to check and compare different coding systems, namely AA, CL and hp-CL with their corresponding substitution matrix, say BLO-SUM, CLESUM and HP-CLESUM. We first compare the TopK accuracy of SFPs (similar fragment pairs) and the neighbor of AFP (aligned fragment pairs) against a large dataset encompassing the protein homologous levels from family to fold according to SCOP [46]; then we embed hp-CL into CLeFAPS [26], replacing the original CL, to get an improvement against the popular benchmark HOM-STRAD [42] .
The conversion from 3D protein structure to 1D CL string. (A) Given a sliding window of length four, may we get four contiguous Cα atoms, and determine two bending angles θ, θ ′ and a torsion angle τ . (B) Select a state which maximize the given data, where each state is a gaussian distribution in the three dimension space of θ, τ, θ ′ . (C) Assign the state (letter) to the third place of the four Cα atoms, so the N length protein will get N − 3 letters finally, and we assign the first two and the last position with a 'blank' letter R.

A. Datasets
We use PDB-SELECT databank [36] to construct our CLs, and use FSSP database [38] to derive the substitution matrix CLESUM. Particularly, PDB-SELECT contains 1544 non-membrane proteins from PDB [37] with amino acid identity less than 25%. FSSP is based on exhaustive all-against-all structure comparison of the representative protein structures, where the representative set contains no pair which has more than 25% sequence identity. A tree for the fold classification of the 2,860 representative set is constructed by a hierarchical clustering method based on the structural similarities. Family indices of the FSSP are obtained by cutting the tree at levels of 2, 4, 8, 16, 32 and 64 standard deviations above the database average.

B. Conformational letter and its substitution matrix
Four contiguous C α atoms, say i − 2, i − 1, i and i + 1, determine two bending angles θ, θ ′ and a torsion angle τ which is the dihedral angle between the two planes of triangles i − 2, i − 1, i and i − 1, i, i + 1 (see Fig. 1). By using a mixture model for the density distribution of the three angles, the local structural states from PDB-SELECT have been clustered as 17 discrete states (see our previous work [14] for more details). To use our SAs directly for the structural comparison, a score matrix similar as BLOSUM [32] for AAs is desired. In details, we first convert the structures of the representative set from FSSP to their CL strings; then collect all the pair alignments with the same first three family indices (DALI Z-Score ≥ 8) (see Fig. 2); finally count all ungapped aligned pairs of CLs to generate the substitution matrix, say CLESUM (Table I). The total number of structures is 10,047 pairs, consisting of 175,723 fragment pairs and 1,284,750 code pairs.

C. Entropic clustering
From FSSP, which contains also the AA information, it is possible to construct a substitution matrix in the joint space of the structure and sequence. However, such matrix would have about (17×20)×(17×20) parameters ( Fig. 3(A)). If we group the 20 AAs into two clusters, then the parameters of the matrix are reduced to (17×2)×(17×2).
Generally, the mutual information I of two discrete

Fragments in FSSP
The i-th fragment

Monte Carlo to group 20 AAs into 2 categories
find maximal I or not?

HP-CLESUM
The i-th fragment If we cluster a i and a j into a i&j leads to The difference between values of I after and before clus-tering is given by and their analogs x j and ω j , then defining From the Jensen's inequality, for the convex function x log x here we have f ( x ) ≤ f (x) , so I never increases after any step of clustering.
That is to say, merging any two members into one cluster will result in a loss of mutual information. To make the loss of mutual information as small as possible, I should be maximized, so it can be naturally chosen as the objective function during clustering. We call this approach entropic clustering [34]. If we partition n objects into m 1 and m 2 classes, where m 2 > m 1 , it is easy to prove that the maximal I at m 2 is always greater than the maximal I at m 1 [23]. Now turning back to our substitution matrix in the joint space, we may define the average mutual information as follows like BLOSUM, where X and Y means a joint state of CL and AA (either reduced or not). Given a clustering group may we calculate its I based on Eq. (5) and according to entropic clustering we should get a categories which maximize I (Fig. 3(F)).

A. Joint substitution matrix of conformational letters and reduced amino acids
For clustering the 20 AAs into two categories, the Monte Carlo finds AVCFIWLMY and DEGHKNPQRST as the groups, which is just the hydrophobic and hydrophilic cluster [35]. Such enlarged CLs are called hp-CLs.

JḢİKṄQLĠṀḂṖȦȮĊĖḞḊ
The substitution matrix of hp-CLs is called HP-CLESUM, this symmetry matrix can be divided into three sub-matrices: CLESUM-hh, CLESUM-pp, and CLESUM-hp. The first two, shown in Table II, correspond to the same hydropathy aligned amino acid types (i.e., h-h and p-p). The third, shown in Table III, corresponds to the different hydropathy types h-p. As expected, compared with the original CLESUM (Table I) A coding system in protein structure is defined as an alphabet combined with its corresponding substitution matrix. Amino acids (AA) or all kinds of SAs can be treated as coding systems, so long as the alphabet has its substitution matrix. We'll compare the performance of the following three ones, namely AA, CL and hp-CL, based on their TopK accuracy against a benchmark (Fig.  4). The difference between SFP and AFP is, we use SFPs to describe all local similar fragment pairs, while AFPs is a subset of SFPs that each of them should be in the final alignment [26].
Note if the length of an AFP, say Len is longer than L, we'll check each positions and the total number is Len − L + 1; if Len is shorter than L, we just skip this AFP. As a result, the TopK SFPs' accuracy of a single pair of structures is a 0 or 1 measure, that is to say, within TopK we find a correct SFP or not. While the TopK neighbor of AFP's accuracy is calculated by summing all correct positions found in any AFPs then dividing the total valid positions, the result is between 0.0 to 1.0.
The benchmark we use is divided in three levels: family, superfamily and fold according to SCOP [46]. In family set, we use all SCOP families which have 2 to 25 mem-bers in ASTRAL 40% compendium [47] and the total pair number is 21,039. In superfamily and fold, it is convenient to use SABmark [43] instead of using ASTRAL 40% because SABmark is systematically arranged and elaborately checked at both superfamily and fold level. The superfamily set contains 3,645 domains sorted into 426 subsets and the fold set (or be called twilight zone [48]) contains 1,740 domains sorted into 209 subsets, where each subsets contain between 3 to 25 structures. The superfamily set contains 18,724 structure pairs and the fold set contains 10,306. We apply MATT [45] to conduct all-against-all pairwise alignment within each family or subset as our gold standard. Table IV shows that, hp-CL performs best while CL follows the second, both of them outperforms 10% to 100% than AA. For details, with the increase of TopK and length L, the accuracy of all coding systems grows better, while from family to fold level, the accuracy declines. It is surprising that at fold level, the accuracy of hp-CL outperforms AA more than 50% at the TopK SFP accuracy test and more than 100% at the TopK neighbor of AFP test, while in the latter, hp-CL got the average accuracy at about 71% given L = 18 from the Top-1 highest neighbor of an AFP. Such feature may be applied to construct the Highest Similarity Fragment Block (HSFB) during the multiple structure alignment [23]. Given a seed structure and a certain position, if this position got many high score neighbors in other structures, may we say that this block (consisting the seed position and its neighbors) has a more probable chance in the final multiple alignment. Moreover, we've shown the effectiveness of parameter self-adaptive strategy to create the SFP-list in [26]. At most cases self-adaptive strategy is compatible with fixed parameters, while the size of the SFP-list can be controlled empirically to about O(n 2 /LEN H/6) with the LEN H=9 (Fig. 5). However, its hard to control the balance between the size of the SFP-list and the threshold of SFP generated with fixed parameters strategy. Actually, the data of fixed length used in Table IV is considered all O(n 2 ) SFPs, then to select TopK; we've tested different SFP thresholds, if it is set too high there'll lead to blank or few SFP-list while if it is set too loose then the SFP-list will be too much (data not shown).

Performance
Finally, we may get the conclusion that, during structure comparison, the only consideration of the TopK highest SFPs to built the initial alignment is feasible from family level to fold, so long as the coding system is specific enough. Also the employment of parameter self-adaptive strategy to generate SFPs is effective and economic.  space (moln1*moln2) between all homologous levels (from family to fold) under the self-adaptive strategy, where the moln1 (moln2) is the first (second) structure's size. The peak value is about 1.045% and the mean value is about 1.5505%. The total pair count is 50,069.

C. Implement of hydropathy conformational letters to structural alignment
We embed hp-CL to the pairwise protein structural alignment problem under the framework of CLeFAPS [26]. Particularly, we first transform each structures to its hp-CL strings; then search for both highly specific SFPs (SFP H) that have a high HP-CLESUM score to build an initial alignment from the best TM-score [39] SFP within TopK, and highly sensitive SFPs (SFP L) that have a low HP-CLESUM score (must above 0) to refine the alignment through fuzzy-add strategy. These two SFP-lists can be generated simultaneously [24]; finally we apply an elongation based on Vect-score to collect local flexible fragments.
HOMSTRAD is a database of protein structural align- ments for homologous families [42]. Its alignments were generated using structural alignment programs, then followed by a manual scrutiny of individual cases. There are totally 1033 families (633 at pairwise level). We'll show the improvement based on hp-CL as the coding systems instead of CL under the same algorithm, say CLeFAPS, in Table V.

IV. DISCUSSION AND FUTURE WORK
To explore the joint space of both AAs and SAs, entropic clustering is a simple but effective approach. In this work, only the reduction of AAs is considered, while we may also reduce CLs and AAs simultaneously while balancing the accuracy and the parameter numbers. For example, if reducing the CL to 9 letters, (actually, from Fig. 1, there are 4 codes for helix which can be grouped to one cluster, the same as sheet.) we may then consider up to four AA cluster instead of two, while the total alphabet number is about the same as hp-CL.
It is interesting that, hp-CL can be applied during the situation we know only a little information about the AA sequence of the structure, i.e., the hydropathy features, or even none. That is true because, from the knowledge of protein design [40,41], the hydropathy patterns from a 3D structure may probably be deduced. Then the usage of hp-CLs and HP-CLESUM that consider the hydropa-thy patterns will get a more accurate result than CLs and CLESUM that only consider the 3D structure.
We also verify a basic idea in CLeFAPS, i.e., selfadaptive strategy to generate SFPs, that we needn't consider the parameters to deal with different purposes and different proteins. The result showed its accuracy is maintained well and the SFP-list size is controlled in O(n 2 /LEN H/6) while its hard to judge the balance between accuracy and size with fixed parameters.
TopK accuracy check has demonstrated the basic strategy of both CLePAPS and CLeFAPS efficient, which only considers TopK highest SFPs to built the initial alignment. Moreover, TopK accuracy check is an effective approach to measure the coding systems against a reference dataset, especially to judge the substitution matrix. If a coding system is good enough, it should rank those SFPs with highly specificities top enough among other SFPs. In a future work, we'll use this approach to test the current available SAs based on their performance for finding specific SFPs. Also we can do the comparison between SAs and RMSD values or some p-values derived from RMSD. Such comparison between 1D coding systems with 3D expression will show the effectiveness of SAs because they contain the statistic information from the database [24].