7 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., self- adaptive strategy to generate SFPs, that we needn’t con- sider 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 be- tween accuracy and size with fixed parameters. TopK accuracy check has demonstrated the basic strat- egy of both CLePAPS and CLeFAPS efficient, which only considers TopK highest SFPs to built the initial align- ment. Moreover, TopK accuracy check is an effective approach to measure the coding systems against a refer- ence 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 sys- tems with 3D expression will show the effectiveness of SAs because they contain the statistic information from the database [24]. This work is supported by ... Acknowledgments References [1] Chothia, C. (1984). Principles that determine the structure of proteins. Annu. Rev. Biochem. 53:537-572. [2] Baker, D. & Sali, A. (2001). Protein structure prediction and structural genomics. Science 294:93-96. [3] Jones, D. (1999). Protein secondary structure prediction based on position-specific scoring matrices. J. Mol. Biol. 292:195-202. [4] Eidhammer, I., Jonassen, I. & Taylor,W.R. (2000). Structure com- parison and structure patterns. J. Comput. Biol. 7:685-716. [5] Offmann, B., Tyagi, M., & de Brevern, A.G. (2007). Local protein structures. Current Bioinformatics 2:165-202. [6] Pauling, L., Corey, R. & Branson, H. (1951). The structure of pro- teins: two hydrogen-bonded helical configurations of the polypep- tide chain. Proc. Natl Acad. Sci. USA. 37:205-234. [7] Pauling, L. & Corey, R. (1951). Configurations of polypeptide chains with favored orientations around single bonds: two new pleated sheets. Proc. Natl Acad. Sci. USA. 37:729-740. [8] Rooman, M., Rodriguez, J. & Wodak, S. (1990). Automatic defi- nition of recurrent local structure motifs in proteins. J. Mol. Biol. 213:327-336. [9] Fetrow, J., Palumbo, M. & Berg, G. (1997). Patterns, structures, and amino acid frequency in structural building blocks, a protein secondary structure classification scheme. Proteins 27:249-271. [10] de Brevern, A., Etchebest, C. & Hazout, S. (2001). Bayesian prob- abilistic approach for predicting backbone structures in terms of protein blocks. Proteins 41:271-287. [11] Kolodny, R., Koehl, P., Guibas, L. & Levitt, M. (2002). Small libraries of protein fragments model native protein structures ac- curately. J. Mol. Biol. 323:297-307. [12] Camproux, A., Gautier, R. & Tuffery, P. (2004). A hidden Markov model derived structural alphabet for proteins. J. Mol. Biol. 339:591-605. [13] Tung, C.H., Huang, J.W. & Yang, J.M. (2007).Kappa-alpha plot derived structural alphabet and BLOSUM like substitution ma- trix for rapid search of protein structure database. Genome Biol. 8:R31.1-R31.16. [14] Zheng, W.M. & Liu, X. (2005). A protein structural alphabet and its substitution matrix CLESUM. Lecture notes in Bioinformatics 3680 (eds. C. Priami and A. Zelikovsky), Springer Verlag, Berlin 2005:59-67. [15] Camproux, A., de Brevern, A., Hazout, S. & Tuffery, P. (2001). Exploring the use of a structural alphabet for structural prediction of protein loops. Theor. Chem. Acc. 106:28-35. [16] Fourrier, L., Benros, C. & de Brevern, A. (2004). Use of a struc- tural alphabet for analysis of short loops connecting repetitive structures. BMC Bioinformatics 5:58-71. [17] Etchebest, C., Benros, C., Hazout, S. & de Brevern, A. (2005). A structural alphabet for local protein structures: improved predic- tion methods. Proteins 59:810-827. [18] Maupetit, J., Gautier, R. & Tuffery, P. (2006). SABBAC: online structural alphabet-based protein backbone reconstruction from alpha-carbon trace. Nucleic Acids Res. 34:W147-W151. [19] Dudev, M. & Lim, C. (2007). Discovering structural motifs using a structural alphabet application to magnesium-binding sites. BMC Bioinformatics 8:106-117. [20] Le, Q., Pollastri, G. & Koehl, P. (2009). Structural alphabets for [38] Holm, L. & Sander, C. (1996). The FSSP database: fold classifi- cation based on structure-structure alignment of proteins. Nucleic Acids Res. 24:206-209. [37] Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H., Shindyalov, I.N. & Bourne, P.E. (2000). The protein data bank. Nucleic Acids Res. 28:235-242. [36] Hobohm, U. & Sander, C. (1994). Enlarged representative set of protein structures. Protein Sci. 3:522-524. [35] Gaboriaud, C., Bissery, V., Benchetrit, T. & Mornon, J.P. (1987). Hydrophobic cluster analysis: an efficient new way to compare and analyse amino acid sequences. FEBS Lett. 224:149-155. [34] Zheng, W.M. (2004). Clustering of amino acids for protein sec- ondary structure prediction. J. Bioinfor. Comp. Biol. 2:333-342. [33] Etchebest, C., Benros, C., Bornot, A., Camproux, A., & de Brevern, A. (2007). A reduced amino acid alphabet for under- standing and designing protein adaptation to mutation. Eur. Bio- phys. J. 36:1059-1069. [32] Henikoff, S. & Henikoff, J.G. (1992). Amino acid substitution ma- trices from protein blocks. Proc. Natl. Acad. Sci. USA. 89:10915- 10919. [31] Murphy, L.R., Wallqvist, A. & Levy, R.M. (2000). Simplified amino acid alphabets for protein fold recognition and implications for folding. Protein Eng. 13:149-152. [30] Miyazawa, S. & Jernigan, R.L. (1993). A new substitution ma- trix for protein sequence searches based on contact frequencies in protein structures. Protein Eng. 6:267-278. [29] Wang, J. & Wang, W. (1999). A computational approach to sim- plifying the protein folding alphabet. Nat. Struct. Biol. 6:1033- 1038. [28] Riddle, D.S., Santiago, J.V., Bray-Hall, S.T., Doshi, N., Grantcharova, V.P., Yi, Q. & Baker, D. (1997). Functional rapidly folding proteins from simplified amino acid sequences. Nat. Struct. Biol 4:805-809. [27] Chan, H.S. (1999). Folding alphabets. Nat. Struct. Biol. 6:994- 996. [26] Wang, S. (2009). CLeFAPS: fast flexible alignment of protein structures based on conformational letters. [25] Liu, X., Zhao, Y.P. & Zheng, W.M. (2009). CLeMAPS: multiple alignment of protein structures based on conformational letters. Proteins 71:728-736. [24] Wang, S. & Zheng, W.M. (2009). CLePAPS: fast pair alignment of protein structures based on conformational letters. J. Bioinform. Comput. Biol. 6:347-366. [23] Zheng, W.M. (2008). The use of a conformational alphabet for fast alignment of protein structures. Lecture notes in Bioinformatics 4983 (eds. C. Priami and A. Zelikovsky), Springer Verlag, Berlin 2008:331-342. [22] Yang, J.M. & Tung, C.H. (2006). Protein structure database search and evolutionary classification. Nucleic Acids Res. 34:3646- 3659. [21] Guyon, F., Camproux, A.C., Hochez, J. & Tuffery, P. (2004). SA-Search: a web tool for protein structure mining based on a structural alphabet. Nucleic Acids Res. 32:W545-W548. protein structure classification: a comparison study. J. Mol. Biol. (2009), doi:10.1016/j.jmb.2008.12.044.