Protein is composed of amino acids which are, in turn, made up of mostly carbon, hydrogen. oxygen, nitrogen. A protein structure consists of thousands of coordinates of its atom. Building structure index tables (often organized by suffix trees or arrays) of proteins is an important phase for quickly searching or classifying protein structures. Most previous studies use only structural features to build the index tables, therefore searching and classifyiug performances based on these index tables are not good enough. In this paper, the authors proposed two methods of feature selection to create index tables that contain not only structural features but also sequantial features. Experiments on a protein classification dataset (called SCOP) showed that our proposed feature selection methods considerably improve the searching and classifying performances when compared with previous feature selection methods.