most of the alignment methods rely on structure comparison to identify structural , evolutionary , and functional relationships between proteins . in general ,
these methods align proteins based on structural similarity . a structural alignment can identify the evolutionary equivalent residues when the aligned proteins share a common ancestor .
unlike sequence alignment tools , which focus on equivalent residues , structural alignment methods focus on conserved protein structure . therefore ,
structural alignment identifies functional mechanisms by comparing functionally related proteins and can also annotate the function of proteins whose structures have been detected .
several protein structural alignment methods [ 28 ] compare protein structures by structural similarity based on secondary structure elements , as well as intra- and intermolecular atomic distances .
the basic idea of structure alignment is to identify the secondary structural elements , cluster these elements into groups , and score the best substructure alignment .
the vector alignment search tool ( vast )   compares protein structures according to the continuous distribution of domains in the fold space .
vast has been used to compare all known protein data bank ( pdb ) domains to each other .
dali   aligns proteins using several 2d distance matrices that represent all intramolecular distances between the c atoms .
it splits the protein sequences into hexapeptide fragments and calculates 2d distance matrices by measuring the contact patterns between consecutive fragments .
dali was used to create the fssp database from 3d structure comparisons of protein structures from pdb .
the combinatorial extension ( ce ) method   operates similarly to dali , in that each protein sequence is fragmented .
a final alignment is calculated as the optimal path through the similarity matrix and is extended with the next highest - scoring aligned fragment pairs .
this algorithm adopts a combinatorial approach to evaluate secondary structural similarities between two protein structures based on contact maps .
ssap   uses a dynamic programming approach based on atom - to - atom vectors in the structure space .
spalign   is a pairwise protein structure alignment method that compares protein sequences using a size - independent scoring function called spscore , which can fix the cutoff distance at 4   .
improvements to structure alignment methods have been actively researched , and new or modified methods have become widely distributed web services .
increasing numbers of protein structure alignment tools are being deployed online , enabling users to submit their data and obtain the final alignments on websites [ 2 , 3 , 6 , 8 ] .   the recently developed service deployment model called cloud computing can deliver computing resources , either hardware or software , via the internet .
the cloud computing platform relies on virtualization technology to concentrate all physical resources into a large resource pool .
hadoop supports a parallel programming model , called mapreduce , that enables parallelization of large datasets .
mapreduce possesses several important characteristics ; namely , high availability , scalability , and fault tolerance . in traditional parallel programming models such as mpi , openmp , and pthread ,
cloudburst   is a parallel algorithm that maps next - generation sequence data to reference genomes .
this algorithm has been adopted in researches such as snp discovery , genotyping , and personal genomics .
sudha sadasivam and baktavatchalam   proposed a hadoop - based multiple sequence alignment method to solve large - scale alignment problems .
another hadoop - based system , crossbow , is a scalable , portable , and automatic cloud computing tool that detects snps among short read data .   in this paper , we propose a cloud service for protein structure alignment .
structural alignment methods based on atom - pairing schemes , such as vast , ce , and dali , require a reliable isometric transformation by which to produce the best atom - pairing alignment between two proteins .
therefore , we introduce a refinement algorithm that uses isometric transformations to compare two protein structures .
the algorithm refines the output of existing structural alignment methods such as vast . in our cloud service , the protein structure alignment and refinement algorithms
is performed in the virtualization cloud environment . by comparing the proposed algorithm with existing protein structural alignment tools
in addition , the computational performance of the proposed service can be enhanced proportionally to the number of hadoop map operations .
protein structure alignment detects homologous polymer structures based on shape and three - dimensional conformation .
protein structural alignment tools detect the evolutionary relationships between proteins by comparing proteins with low sequence similarity . in general , the outputs of a structural alignment tool are a superposition of the atomic coordinate sets and the minimum root mean square deviation ( rmsd ) between the structures .
let t = ( t1 ,  , tn ) and l = ( l1 ,  , ln ) be two sequences of points .
the ith ( x , y , z ) coordinate value of a point in x is denoted by xi , and |x| denotes the length of x. let d be the rmsd function which produces the rmsd value , then 
 ( 1)d(t ,  l ,  r ,  )=1nk=1n|rtk+lk|2 , 
 where r is a rotation matrix and  is a translation vector .
the minimum rmsd value d(t , l ) between t and l is defined as d(t , l ) = min{d(t , 
l ,  r ,  )}. the proposed cloud computing service for protein structure alignment comprises two main stages : structural alignment and alignment refinement .
our platform uses two widely used protein structure alignment algorithms , dali   and vast .
the proposed cloud service not only provides structural alignment but also develops a refinement algorithm to reduce the rmsd of the original alignment .
this stage consists of three steps : isometric rotation transformation , minimum bipartite matching , and angle triplet adjustment , as described below .
the parameter input to the rmsd scoring function is the rotation matrix r. to achieve a small rmsd score , this rotation matrix must be provided in a protein structure alignment .
euler 's rotation theorem   states that any rotation about the origin can be expressed as three angular parameters .
a rotation matrix is defined in terms of two axes ( x , z ) and three euler angles (  ,  , and   ) .
firstly , angle  rotates around the z - axis ; next , angle  rotates around the x - axis , followed by a third rotation through angle  around the z - axis . given a unit vector n = ( 0,0,1 ) , and the rotation matrix , r , n is rotated to another unit vector p = ( x , y , z ) , that is , p = rn .
two angles ,  and  , determine the z - coordinate of p and the x- and y - coordinates of p , respectively .
a rotation r can be made by rotating all other points around the vector p by the angle . in general , a rotation transformation is parameterized by an angle triplet (  ,  , and  ) .
thus , a vector p = ( x , y , z ) on the surface of the unit sphere is a probe .
each probe is shifted from vector ( 0,0,1 ) to other points within the sphere .
the position of p is decided by two angles (  ,  ) , and its rotation is decided by the angle .   the rotation matrix is characterized by adjusting the three distributed angles (  ,  , and  ) . similar to euler 's rotation transformation , the rotation through the angle triplet (  ,  ,  ) is achieved as follows .  

first rotation . given a unit vector p = ( x , y , z )
, p is transformed into p by rotating the z - axis through angle . p = ( x,y,z ) . more precisely 
 ( 2)p=[c1s10s1c10001]p , 
 where c1 and s1 denote cos and sin , respectively . 

the vector p is transformed into the probe p by rotating an angle  around the x - axis with p = ( x,y,z ) ; more precisely 
 ( 3)p=[1000c2s20s2c2]p , 
 where c2 and s2 denote cos and sin , respectively . 
 third rotation .
that is , 
 ( 4)r=[c3+x2hxyhzs3xzh+ys3xyh+zs3c3+y2hyzhxs3xzhys3yzh+xs  3  c3+z2h ] , 
 where c3 and s3 denote cos and sin , respectively , and h = 1  cos. the rotation matrix r , which determines the rmsd value , is calculated after three self - rotations in the above example . since the number of rotations is unlimited , many rmsd values can be computed from rs calculated by various sets of unit vectors .  

since smaller rmsd value implies higher structural alignment accuracy , the proposed refinement algorithm seeks an alignment that minimizes the rmsd .
the minimum bipartite matching algorithm identifies the two sets of unit vectors with the smallest rmsd value .
the mass centers of p and q remain at their respective original locations p and q. giving a weighed graph g = ( v , e ) , v is labeled with points of p and q , and each ( p , q ) in e is weighted by the squared euclidean distance .
although minimum bipartite matching identified the smallest rmsd values from various rotations , the rmsd is reduced further by adjusting unit vectors with angle triplets . in this step ,
the angles  ,  , and  are sequentially adjusted , and the evaluation function f( ) corresponds to the rmsd values altered by the adjustments .
the f( ) is defined as follows : 
 ( 5)f()=c1+(i=2kcicosi+ci+1  sini ) , 
 where k is the number of local maximum vectors and  = (  ,  ,  ) .
the adjusted angles evaluated by f( ) constitute the new parameters in the isometric rotation transformation .
most existing alignment tools are computationally time consuming and are best implemented under powerful parallel processing . moreover
the protein structure alignment and the proposed refinement algorithm are implemented in hadoop and are deployed on a virtualized computing environment .  
many cloud computing vendors , such as yahoo , amazon ec2 , ibm , and google , have supported the map / reduce model .
an application implemented by this model comprises map and reduce stages , as shown in figure 2 .
the input data is first split into smaller chunks corresponding to the number of mappers .
the < key , value > pairs are classified by key and are assigned to a corresponding reducer . in the reduce stage ,
the reducer sums all values belonging to the same key among the assigned < key , value > pairs . the reduce stage outputs < key , value > pairs , where each key is unique .  
the master node consists of a job tracker , task tracker , name node , and data node .
a slave node , or computing node , comprises a data node and task tracker .
the job tracker distributes map / reduce tasks to specific nodes in the cluster , ideally to those nodes already containing the data , or at least within the same rack .
a task tracker is a node in the cluster that accepts map , reduce , and shuffle operations from a job tracker .
hadoop distributed file system ( hdfs ) is the primary file system used by the hadoop framework .
hadoop evades faults by creating multiple replicas of data blocks and distributing them to data nodes throughout a cluster , thereby enabling reliable , extremely rapid computations .
the physical resources , including computing power , storage and network , are regarded as utilities that users can pay for as required .
the usual goal of virtualization is to improve scalability and overall hardware - resource utilization .
virtualization enables the simultaneous running of operating systems in a single physical computer . while a physical computer constitutes a complete and actual machine , a virtual machine ( vm ) is a completely isolated machine running a guest operating system within the physical computer .
all nodes within a hadoop cluster of the proposed cloud service , such as job tracker , task tracker , name node , and data nodes , operate in virtual machines .  
the wwpdb ( protein data bank )   is a widely accessed database that archives experimentally determined structures of proteins , nucleic acids , and complex assemblies .
the submitted pdb i d pair is stored in a job queue file . assuming that n task trackers must distribute p pdb i d pairs in the job queue file , the ith line in the queue file will as assigned as the ith map task and sent to hadoop by streaming operation . each task - tracker node receives a map task which aligns the protein structure and executes the refinement algorithm .
the refined alignment is converted to a 3d protein structure image using the pdb2vrml tool . when a task - tracker node has completed a map task
generally , each task - tracker node is assigned p / n map tasks . in the proposed cloud computing service , the reduce task that collects the rmsd value of each pbd i d pair is performed solely by the reducer . finally , the reducer stores the rmsd values in a file by hdfs .
the proposed cloud computing service for protein structure alignment can be regarded as baas ( bioinformatics as a service ) .
the proposed service , accessible through the internet , enables molecular biologists to efficiently execute 3d protein structure alignment .
supplied with two user - input pdb ids , the service searches protein structure data archived in the wwpdb and compares the protein structures using hadoop .  
the proposed service provides users with a hyperlink for accessing the alignment result before the computation is complete . in this way
figure 5 shows the submitted job information , including the hyperlink enabling result download .  
figure 6 shows the output of the proposed service , including a 3d structural image of the protein   and rmsd values .
each server is equipped with two quad - core intel xeon 2.26  ghz cpus , 24  gb ram , and 296  gb hard drive . under the current system environment
, we create 8 virtual machines by kernel - based virtual machine ( kvm ) ; each virtual machine is set to one single - core cpu , 2  gb ram , and 30  gb hard drive and runs hadoop version 0.2 .
protein structure data sources used in the experiments were downloaded from the world wide protein data bank ( http://www.wwpdb.org/ ) .
the protein data bank contains 80,402 protein structures , from which 1000 protein pairs were selected as test data by uniform - random sampling .
the comparison between the original rmsd values produced by dali and vast and the refined values of our proposed algorithm is summarized in table 1 .
the rmsd values produced by dali and vast were improved using isometric rotation transformation and bipartite matching .
the improved alignments can also be improved in advance by angle triplet adjustment , as seen in table 1 .
our approach improved the rmsd values of dali and vast by approximately 7% and 6% , respectively .
clearly , the proposed refinement algorithm can significantly improve the rmsd values produced by standard protein structure alignment methods .   to assess the performance of the proposed cloud service based on the hadoop framework , the execution time of the service
was compared for varying structural data size and number of map / reduce operations .  
the execution time is effectively reduced when more map operations are deployed . compared to the sequential algorithm ( implemented in the proposed service with a single mapper ) , introduction of two , four , and eight mappers improved the execution time by approximate factors of two , four and eight .
the computation efficiency is improved by an amount proportional to the number of mappers , although the execution time increases as the number of protein pairs and protein atoms increases ( see figure 7 ) .
several online alignment tools are currently available for comparing protein structures . these methods are widely used in bioinformatics , but their implementation on a single computer limits their computing power and data availability . to remedy this situation , we propose a novel biocloud service for protein structure comparison based on virtualization technology and the hadoop framework .
we also propose an algorithm for refining the alignment produced by standard protein structural alignment tools such as dali and vast .
our service provides molecular biologists with a high performance , fault tolerant , and high - availability protein structure analysis platform .
the proposed cloud service was experimentally verified as suitable for investigating protein structure functions . in future work
, we will investigate an automatic deployment model that dispenses bioinformatics tools as cloud computing services . the hadoop framework and
virtualization technology ensures high performance in a robust computing environment . due to the scalability of our platform
 protein structure alignment has become an important strategy by which to identify evolutionary relationships between protein sequences . 
 several alignment tools are currently available for online comparison of protein structures . in this paper 
 , we propose a parallel protein structure alignment service based on the hadoop distribution framework . 
 this service includes a protein structure alignment algorithm , a refinement algorithm , and a mapreduce programming model . 
 the refinement algorithm refines the result of alignment . to process vast numbers of protein structures in parallel , 
 the alignment and refinement algorithms are implemented using mapreduce . 
 we analyzed and compared the structure alignments produced by different methods using a dataset randomly selected from the pdb database . 
 the experimental results verify that the proposed algorithm refines the resulting alignments more accurately than existing algorithms . 
 meanwhile , the computational performance of the proposed service is proportional to the number of processors used in our cloud platform . 
1. Introduction
2. Materials and Methods
3. The Cloud Computing Platform
4. Experiment
5. Conclusion