arXiv:1001.2879v2 [q-bio.QM] 18 Jan 2010 Hydropathy Conformational Letter and its Substitution Matrix HP-CLESUM: an Application to Protein Structural Alignment Sheng Wang 1 , ∗ $^{1}$Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China Contact*: wangsheng@itp.ac.cn 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) 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. Proteins fold into specific spatial conformations to per- form their biological functions [1] and there are abundant evidences to show their amino acid (AA) sequences de- termining the structures [2]. The attempt to find the relationship between structure and sequence is a funda- mental task in computational biology [4]. Compared to the sequence world which is discrete of 20 AAs, the structure world is continuous, though the lo- cal conformational space of a protein backbone fragment is rather limited [5]. The idea of representing the back- bone 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 confor- mations 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 descrip- tion 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 pro- posed the idea that representing protein structures as a series of overlapping fragments, each labeled with a sym- bol, which defines a structural alphabet (SA) for proteins [8–13]. Such alphabet can be used to predict local struc- ture [15–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] struc- ture 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 en- tropic clustering [34]. Briefly, given two discrete distri- butions 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 re- sult of hydrophobic and hydrophilic, which agrees with HP-model [35] exactly. Then we construct a joint substi- tution matrix HP-CLESUM with (17 ∗ 2) 2 indices by the similar means as constructing CLESUM. The following tests are employed to check and com- pare 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] . I. INTRODUCTION