the number of protein structures deposited into the protein data bank ( pdb ) has more than doubled in the past 5 years ( ) . this trend is partly due to the advances in high - throughput crystallography techniques ( 1 ) as well as the protein structure initiative ( ) funded by the nigms ( 2 ) . to classify and analyze such rapidly growing number of protein structures ,
several structure family databases exist ( 38 ) where each database uses a different set of criteria for classification .
for example , scop ( structural classification of proteins ) database ( 3 ) classifies proteins of known structure based on their evolutionary and structural relationship , whereas cath ( 4 ) uses a hierarchical order at four major levels , i.e. class ( c ) , architecture ( a ) , topology ( t ) and homologous superfamily ( h ) .
structure - based alignment of the members of these families is the key for identifying the structurally conserved domains and patterns .
protein structure comparison servers , such as fssp ( families of structurally similar proteins ) ( 5 ) and ce ( combinatorial extension ) ( 6 ) provide alignments between structural neighbors in the pdb based on exhaustive all - to - all pairwise comparisons .
other resources such as homstrad ( homologous structural alignment database ) provide multiple structure alignments for a selected set of families that do not include all pdb chains ( 8) . nevertheless , there are no web resources that offer multiple structure alignments for all pdb chains classified by different criteria .
we developed the ce - mc algorithm for the alignment of multiple protein structures based on monte carlo ( mc ) optimization ( 9,10 ) , ce - mc web server for computing alignments online and ce - mc standalone software for local installation ( 11 ) .
computing multiple structure alignments for larger families is very time - consuming ; hence , here we present dmaps , a database of multiple alignments for protein structures that provides instant access to pre - computed multiple structure alignments for all possible protein chains in the pdb as classified by scop , cath , ce and enzyme databases .
ce - mc program works based on two independent algorithms , i.e. ce and mc optimization . ce algorithm ( 6 ) generates all - against - all pairwise alignments for all chains in a given family and the chain with the highest average z - score ( over the alignments to the other family members ) is selected as the  master  chain , while the remaining chains in the family are designated as 
, mc algorithm assembles the seed alignment in a  master - slave  fashion and performs the optimization process as described in guda et al .
global optimization of multiple alignments is accomplished by random and iterative exploration of the search space with occasional excursions into the non - optimal territory , until the optimization converges .
protein structure families have been obtained from four different sources which use non - overlapping criteria for classification .
these include scop ( 12 ) , cath ( 13 ) , enzyme ( 14 ) and ce classifications ( 15 ) . although cath and scop use evolutionary and topological features for classification , enzyme classification is based on the functional similarities ( with identical ec number ) and ce classification is purely based on the substructure similarities using c- coordinate distances .
scop database ( release 1.67 ) includes 24  037 pdb entries corresponding to 50  285 individual chains , excluding non - protein entries and theoretical models .
each entry in the scop database is classified in the hierarchical order of class  fold  superfamily  family  protein domain  species  pdb entry .
dmaps database contains multiple structure alignments for all pdb entries at each protein domain level .
cath database ( release 2.6.0 ) considers nmr structures and those crystal structures with resolution better than 3.0  , excluding all non - protein and 
cath uses a hierarchical classification of protein domain structures as class ( c ) , architecture ( a ) , topology ( t ) , homologous superfamily ( h ) and sequence families ( s ) with sequence identity > 35% .
dmaps provides alignments at the s - level for 22  478 pdb entries corresponding to 45  414 individual chains .
enzyme database ( release 37 ) classifies enzymes with known structures in the pdb based on their enzyme classification ( ec ) numbers reflecting pure functional similarities .
this release contains 15  106 pdb entries that include only nmr and crystal structures excluding theoretical models .
the last dataset of pdb families was obtained from ce classification based on the substructure homologies ( 15 ) . in this case
, pdb chains were aligned all - against - all in a pairwise fashion and neighbors with z - score > 4.0 and rmsd ( root mean squared deviation ) < 3.0  have been assembled into clusters of common substructures . in all the datasets above , if the size of a family exceeds 50 , we selected chains only from unique pdb entries to reduce redundancy .
after the first filtering , if the number still exceeds 50 , only the first 50 members were used for computing multiple structure alignments .
however , the filtered chains have been indexed to their original family number to facilitate retrieval of multiple alignments for corresponding family .
multiple structure alignments have been generated for all structure families described above , using our ce - mc standalone software ( 11 ) ( available for download from the ce - mc web server at ) .
ce - mc source code has been compiled and run on a dell four - node cluster with dual xeon 64-bit , 3.2 ghz cpus per node , running on fedora core 3 linux os .
automated multiple alignments have been generated for all structural families containing at least three member chains .
ce - mc program automatically filters out those protein chains with average z - score < 4.0 to include only structurally homologous proteins in the multiple alignments .
ce - mc output comes in text format by default and several intermediate scripts have been developed to reformat the alignment in other user - friendly formats including fasta and joy - based formats
. joy program ( 16 ) uses 3d coordinates from pdb files to calculate secondary structural and local environmental features and displays the same in a color - coded format in the sequence alignment .
ce - mc program works based on two independent algorithms , i.e. ce and mc optimization . ce algorithm ( 6 ) generates all - against - all pairwise alignments for all chains in a given family and the chain with the highest average z - score ( over the alignments to the other family members ) is selected as the  master  chain , while the remaining chains in the family are designated as 
, mc algorithm assembles the seed alignment in a  master - slave  fashion and performs the optimization process as described in guda et al .
global optimization of multiple alignments is accomplished by random and iterative exploration of the search space with occasional excursions into the non - optimal territory , until the optimization converges .
protein structure families have been obtained from four different sources which use non - overlapping criteria for classification .
these include scop ( 12 ) , cath ( 13 ) , enzyme ( 14 ) and ce classifications ( 15 ) . although cath and scop use evolutionary and topological features for classification , enzyme classification is based on the functional similarities ( with identical ec number ) and ce classification is purely based on the substructure similarities using c- coordinate distances .
scop database ( release 1.67 ) includes 24  037 pdb entries corresponding to 50  285 individual chains , excluding non - protein entries and theoretical models .
each entry in the scop database is classified in the hierarchical order of class  fold  superfamily  family  protein domain  species  pdb entry .
dmaps database contains multiple structure alignments for all pdb entries at each protein domain level .
cath database ( release 2.6.0 ) considers nmr structures and those crystal structures with resolution better than 3.0  , excluding all non - protein and 
cath uses a hierarchical classification of protein domain structures as class ( c ) , architecture ( a ) , topology ( t ) , homologous superfamily ( h ) and sequence families ( s ) with sequence identity > 35% .
dmaps provides alignments at the s - level for 22  478 pdb entries corresponding to 45  414 individual chains .
enzyme database ( release 37 ) classifies enzymes with known structures in the pdb based on their enzyme classification ( ec ) numbers reflecting pure functional similarities .
this release contains 15  106 pdb entries that include only nmr and crystal structures excluding theoretical models .
the last dataset of pdb families was obtained from ce classification based on the substructure homologies ( 15 ) . in this case
, pdb chains were aligned all - against - all in a pairwise fashion and neighbors with z - score > 4.0 and rmsd ( root mean squared deviation ) < 3.0  have been assembled into clusters of common substructures .
in all the datasets above , if the size of a family exceeds 50 , we selected chains only from unique pdb entries to reduce redundancy .
after the first filtering , if the number still exceeds 50 , only the first 50 members were used for computing multiple structure alignments .
however , the filtered chains have been indexed to their original family number to facilitate retrieval of multiple alignments for corresponding family .
multiple structure alignments have been generated for all structure families described above , using our ce - mc standalone software ( 11 ) ( available for download from the ce - mc web server at ) .
ce - mc source code has been compiled and run on a dell four - node cluster with dual xeon 64-bit , 3.2 ghz cpus per node , running on fedora core 3 linux os .
automated multiple alignments have been generated for all structural families containing at least three member chains .
ce - mc program automatically filters out those protein chains with average z - score < 4.0 to include only structurally homologous proteins in the multiple alignments .
ce - mc output comes in text format by default and several intermediate scripts have been developed to reformat the alignment in other user - friendly formats including fasta and joy - based formats .
joy program ( 16 ) uses 3d coordinates from pdb files to calculate secondary structural and local environmental features and displays the same in a color - coded format in the sequence alignment .
currently , multiple structure alignments are available for 3050 scop- , 3087 cath- , 664 enzyme- and 1707 ce - based families . under each classification , pdb chains belonging to one or more families are indexed to enable easy retrieval . in cases where a pdb chain belongs to multiple families ,
queries may be made by entering any pdb chain i d such as 1cdk : a for multiple chain entries or 1ak1 : _ for single chain entries .
a cgi script finds corresponding family or families for any given pdb chain i d and displays hyperlinks to view or download the results .
hyperlinks to the source pages of family classifications and pdb files are also displayed in the results page ( figure 1 ) .
multiple alignments can be downloaded in six different formats , i.e. joy - html , text , fasta , pdb , joy - postscript and joy - rich text .
the file in pdb format contains superimposed coordinates for multiple alignments that could be directly imported into 3d visualization programs such as pymol ( ) .
in the dmaps database , we generated multiple alignments for proteins belonging to protein domain level in scop and sequence family level in cath .
typically , these classification levels consist of protein domains that share very similar sequences and structures and hence the alignments generated in these two cases are usually unambiguous .
however , alignments built based on the enzyme classification have functional significance whereas those from ce classification are based on the substructure similarities .
dmaps database has been developed to provide quick access to multiple structure alignments for all protein families in the pdb .
building structure alignments using the ce - mc algorithm is time - consuming as the computational time grows quadratic to the number of chains in the family .
hence , alignments have been pre - computed , indexed and stored in flat files for ready access from the web interface . as shown in table 1 ,
automated alignments have been successfully generated for 80% of the cath , scop and enzyme families and 100% of the ce families containing at least three members .
for some families , we could not compute the alignments and similarly for some , joy formatting could not be carried out owing to unidentified bugs in the program code .
we are in the process of fixing these bugs and in the near future , we hope to update the dmaps database with multiple alignments for all structural families in pdb containing at least three members .
current structure databases , such as homstrad ( 8) , dali ( 17 ) , pali ( 18 ) and pass2 ( 19 ) , also provide structural alignments for pdb entries , but several limitations exist in their usability compared with the dmaps database .
for instance , homstrad provides multiple alignments only to representative members of a family while pass2 covers only 628 multimember families .
however , pali builds multiple alignments progressively from pairwise alignments whereas dali offers only pairwise alignments based on all - against - all comparison of 3d coordinates in the pdb .
the unique features of dmaps database are as follows : it offers instant access to multiple structure alignments for thousands of protein families classified by several functional and structural criteria , and the alignments are available in a variety of formats for further use . the dmaps database will be useful for an array of research projects in structural bioinformatics , such as building structure - based family profiles and patterns , improving the quality of sequence alignments and finding remote homologues .
 the database of multiple alignments for protein structures ( dmaps ) provides instant access to pre - computed multiple structure alignments for all protein structure families in the protein data bank ( pdb ) . 
 protein structure families have been obtained from four distinct classification methods including scop , cath , enzyme and ce , and multiple structure alignments have been built for all families containing at least three members , using ce - mc software . 
 currently , multiple structure alignments are available for 3050 scop- , 3087 cath- , 664 enzyme- and 1707 ce - based families . 
 a web - based query system has been developed to retrieve multiple alignments for these families using the pdb chain i d of any member of a family . 
 multiple alignments can be viewed or downloaded in six different formats , including joy / html , text , fasta , pdb ( superimposed coordinates ) , joy / postscript and joy / rtf . 
 dmaps is accessible online at . 
INTRODUCTION
DATABASE DEVELOPMENT
CE-MC algorithm
Datasets for protein structure families in PDB
Building multiple alignments
DATABASE ACCESS
DISCUSSION
Figures and Tables