September 4, 2009

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-Seo1

A METHOD FOR EFFICIENT EXECUTION OF
BIOINFORMATICS WORKFLOWSJUNYA SEO1
j-seo@ist.osaka-u.ac.jp

YOSHIYUKI KIDO2
y-kido@ist.osaka-u.ac.jp

YOICHI TAKENAKA1
takenaka@ist.osaka-u.ac.jp

SHIGETO SENO1
senoo@ist.osaka-u.ac.jp

HIDEO MATSUDA1
matsuda@ist.osaka-u.ac.jp

1 Department of Bioinformatic Engineering, Graduate School of Information Scienceand Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan
2 The Center for Advanced Medical Engineering and Informatics, Osaka University,

2-2 Yamadaoka, Suita, Osaka 565-0871, Japan
Eﬃcient execution of data-intensive workﬂows has been playing an important role inbioinformatics as the amount of data has been rapidly increasing. The execution of such
workﬂows must take into account the volume and pattern of communication. Whenorchestrating data-centric workﬂows, a centralized workﬂow engine can become a bottleneck to performance. To cope with the bottleneck, a hybrid approach with choreography
for data management of workﬂows is proposed. However, when a workﬂow includes many
repetitive operations, the approach might not gain good performance because of the overheads of its additional mechanism. This paper presents and evaluates an improvementof the hybrid approach for managing a large amount of data. The performance of the
proposed method is demonstrated by measuring execution times of example workﬂows.
Keywords: web service, workﬂow, data transfer, database.

1. Introduction
Eﬃciently executing large-scale and data-intensive workﬂows common to scientiﬁcapplications must take into account the volume and pattern of communication.
Traditionally, two common architectures for implementing workﬂow are proposed.
Those are centralized orchestration and choreography [3].
Figure 1 shows the two traditional architectures. Centralized orchestration describes how services can interact at the message level, with an explicit deﬁnitionof the control and data ﬂows. This architecture has a workﬂow engine to execute
workﬂows. The engine acts as a controller of the involved services. Both control
and data ﬂow messages are passed through this central engine. Examples of suchengines in bioinformatics domain are Taverna [6] and Triana [8].
On the other hand, a choreography model describes a peer-to-peer collaboration
between collections of services. This architecture basically does not have a centralized engine that controls workﬂows. Choreography focuses on message exchange, allinvolved services are aware of their partners and when to invoke operations. The

September 4, 2009

2

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoJ. Seo et al.

"$.#&( /1%02' (#4)3 * ' + ,( )#' - + 56%

    

Fig. 1.

"0256( #58( )9&0: !

 ; )' )=<1* 5&>

7 ?@56( ACB * 5>D"&5%' ( 56*

Traditional architectures for workﬂow execution.

#%$&' ( )Fig. 2.

 !

  
*+-,/.%0*/+-,/.%0*+-,/.10   
2%354 376!8 9:! "
;<9 ' =-> 8 9?:A@?9B!4 ' 98

Hybrid architecture of centralized orchestration and choreography.

Web Services Choreography Description Language (WS-CDL) [4] is an XML-based
language for describing this model.
Centralized control is suitable for scientiﬁc workﬂows because those workﬂows
contain many services with complicated controls (such as conditional branches).
However, in a centralized engine, every resulting output of each service is sent backto the engine. Thus the engine can easily become a performance bottleneck by theconcentration of returning data. While a choreography architecture can optimize
data transport between services, but the implementation of this architecture ishighly complex and rigid.
Baker et al. proposes a hybrid architecture that combines an orchestration witha centralized controller (a workﬂow engine) and a choreography model of distributed
data transport [2]. Figure 2 shows an image of the architecture. The architecture
mixes beneﬁts of the above two architectures. It introduces proxies between Web
services and a workﬂow engine. The engine sends a request to a proxy instead ofa service. The proxy invokes the service and save its result to a local storage, andreturns a unique ID of the result to the engine. The result (intermediate data) is
not sent back to the engine but is transferred directly to other proxies according
to the data ﬂow in the workﬂow. Therefore the engine does not have to receive theintermediate data to be sent to the next service.
In this paper, we propose a modiﬁcation of the hybrid architecture. The hybrid

September 4, 2009

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoEﬃcient Execution of Bioinformatics Workﬂows

8G!5H, I
J E-  +"!. % &#'( )0/

:  4+

3=/ ,  +-?> A@3B8C



--  "!#132 4*65

-. % &#'( < /

-;:  4+D  ;&64+E  "!#$% &#'( )% +*'(, &F(A@3B8C

 

Fig. 3.

-  7 +8!#- $7% &#'( )% *'9, & 

Execution steps of a workﬂow with two Web services in the original hybrid architecture.

architecture can suppress the amount of data transfer by removal of the transfer
to/from the engine. Thus its performance is highly improved when the amount of
the resulting output of each service is very large. However, some overheads exist in
the hybrid architecture at the proxies. When it is adopted to a workﬂow including
repetitive operations (such as loop operations), the engine need to frequently interact with proxies for invoking services and transferring their results to other proxies.
We change the protocol between the engine and proxies for reducing the overheads
as described in Sec. 3.
2. Workﬂow Operations in Hybrid Architecture
Workﬂows are frequently used in various scientiﬁc ﬁelds. Especially, in the bioinformatics domain, workﬂows can be used for integrating a number of remote resourcesin terms of data and applications [1]. Many analysis tools are available as Web
services from EBI [5, 9], DDBJ [10], and KEGG [11]. Scientists often use several
databases for their analyses and compose workﬂows with several Web services thatare distributed geographically.
Figure 3 shows the execution steps in a workﬂow containing two Web services
in the hybrid architecture [2]. Those steps are described as follows in detail.
1: A workﬂow engine invokes a proxy to make an invocation to a Web service(Fig. 3 left).
2: The proxy invokes the Web service.
3-4: The proxy receives the result of the service, and save it within the proxy.
There is a requirement that the proxy has enough disk space to store theresult.
5: The engine receives only the ID of the result from the proxy instead of its
whole data.

September 4, 2009

4

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoJ. Seo et al.

  1 ')( !
2 '$, -*./ ( 38')( $*

&')( *+'), -*./ , 0./  

Fig. 4.

4 '!5 607%

1>= ':, -*./ ( 3<' 6!

9 ':( *;/':, $-*./ , 0./ "#$% 

Modiﬁed execution steps of a workﬂow in the proposed hybrid architecture.

6: The engine invokes the proxy again to make transfer the result (the operation
is named deliver in Fig. 3).
7: The proxy invokes another proxy (Fig. 3 right) to notify data transfer.
8: The second proxy receives the result from the ﬁrst proxy (the operation isnamed stage in Fig. 3).
9-10: After the data transfer ﬁnished, the second proxy returns acknowledgmentto the ﬁrst proxy, and the ﬁrst one also returns it to the engine.
11-15: The engine invokes the second proxy with the ID, and the second proxyinvokes another Web service.
As shown in Fig. 3, additional invocation steps are necessary compared witha centralized orchestration (2, 6, 7, and 12). If the workﬂow includes repetitive
operations, those extra invocations are carried out at the number of repeats. The
extra invocations may increase the processing time of the workﬂow.
3. Improved Method
As the amount of biological databases has been increasing rapidly, the data to
be managed in workﬂows has also been increasing. Those databases contain huge
numbers of entries. For example, there are over 9 million entries are registered in the
UniprotKB database [12]. When scientists want to analyze such a huge number ofdata in their workﬂows with Web services, repetitive invocations of the services are
occurred. If they use several databases in combination, the total number of resulting
data should be very large. Those repetitive invocations in a workﬂow cause large
overheads in the hybrid architecture.
To decrease the number of the extra operations described in the previous section,
we present a modiﬁcation to change the execution steps in the hybrid architecture.
The modiﬁed execution steps are described as the followings (see Fig. 4).

September 4, 2009

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoEﬃcient Execution of Bioinformatics Workﬂows

5

1: A workﬂow engine invokes a proxy to make an invocation to a Web service(Fig. 4 left).
2: The proxy invokes the Web service.
3-4: The proxy receives the result of the service, and transfers it to another proxy(Fig. 4 right).
5: The engine receives only the ID of the result from the ﬁrst proxy instead ofits whole data.
6-11: The engine invokes the second proxy with the ID, and the second proxyinvokes its Web service. If it is not necessary to transfer the result of the
Web service to other proxies, the proxy saves the result within the proxy.
In the proposed modiﬁcation of the execution steps, we decrease overhead at thefollowing two points:• Transfer the result of a Web service to the next proxy directly.
A proxy transfers the result to the next proxy directly. In this case, the proxydoes not need to save the result within the proxy. Thus one step is removed
from previous hybrid architecture (Step 4 in Fig. 3).
• Remove deliver and stage operations.
By transferring the result directly, the workﬂow engine and the ﬁrst proxydoes not need to invoke the ﬁrst proxy and the second proxy, respectively,
to make transfer the result. Thus deliver and stage operations and receiving
their acknowledgments (Steps 6, 7, 9 and 10 in Fig. 3) can be removed.
Totally we can remove two Web service invocations and one data saving within
the ﬁrst proxy. The proxy we have proposed is deployed as a Web service as thesame as the original hybrid architecture. Figure 5 shows the deployed operation in
our proxy. Our proxy has only one operation to invoke a Web service and to makedata transfer.
The operation “invoke” receives 4 arguments. “wsdl”, “operation” and “args”
are the same as those in the original hybrid architecture. There is a diﬀerence atargument “returns”. Our operation can handle multiple results so that the workﬂow
engine can extract resulting data to be returned. The destination information of thedata transfer is also included in “returns” like:resultA->hybrid.ist.osaka-u.ac.jp
resultB->http://hybrid.ist.osaka-u.ac.jp:8080/axis2/services/Hybrid?wsdl
Users can specify transferring destination as its host name or WSDL location.
Users also can specify diﬀerent destinations in each result.

September 4, 2009

6

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoJ. Seo et al.

     !#"%$'& ( )*,+  (- .,/+0$(1 .2314)$6507
8:9;"%$'& <= $?>@.A?BC 1+1 /DE.+*"FD$'0G 1H
8:9G+14 )<D $?G+14 IG+JKK*LGM"FD$'0G NH
8:9+OG$P<= $I+D  $EQ+0JR $1H
8:9 S14.4)$<: $-+F  $E-S14M)+ $T+&D+012+)&&S$;$C M+$PE0ULGVS$N H

W L $-,+  IS14)$:+D  $E X A$=1S$1GG&F%LG%)+ )$Y$1G) E4 )&KF9 S14)$<Fig. 5.

Deployed operation in the modiﬁed proxy.

4. Experimental Result
4.1. Experiment with Test Web Services
In order to evaluate the proposed method, we have carried out performance analysis
tests. In this analysis test, we prepared two test Web services.
• WS1 (Data Generate Service): This service receives an integer as its parameter, and generates a random string whose length is the parameter andreturns them.
• WS2 (Echo Size Service): This service receives a string and returns its size.
We set two proxies and one workﬂow engine. The two proxies are located in thesame local area network to the two Web services, respectively. The engine is set at a
distant place from those proxies so that the engine communicates with the proxies
through a wide area network. We composed a simple workﬂow that generates astring and counts the size. First, the engine calls WS1 and gets a string. After that,the engine passes the string to WS2.
We compare our method with a centralized orchestration and the original hybridarchitecture changing the data size and the number of data.
Figure 6 shows the result of small data in the experiment. The data size varies
from 1k to 1000k bytes per 100k bytes. In this experiment, the workﬂow handles
only one single data.
In both the original and the proposed hybrid architectures, there is an initial
overhead when the workﬂow engine invokes a proxy instead of a Web service, but
the data transfer time sending its result back to the engine can be reduced since theresult can send it to another Web service via their proxies without sending throughthe engine. It is to be noted that we assume a Web service and its proxy are locatedwithin the same local area network and the data transfer speed between them isfast.
If the size of the resulting data is larger, the data transfer overhead via the engine
is getting larger in the centralized orchestration architecture. Thus the execution
time of the centralized one is longer than those of the two types of the hybridarchitecture when transferring data size is more than 400k bytes as shown in Fig. 6.

September 4, 2009

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoEﬃcient Execution of Bioinformatics Workﬂows

7

  
 
  

!


 



 



 









 



 



 "$#&%'#)(+* ,-/.1032+4
5 -+67% 89#3: * ,-<;=>89* ?+* 63#+: @BADCE89* ;FE8'GIH+GEJ -<;>@KAECD89* ;Fig. 6.

Execution times on small data.






#"
!


 











$%'&(%)+* ,-.(/0+1

2 -435&67%48 * ,-:9Fig. 7.

;<6=* >4* 34%+8?A@CBD6=* 9

ED67FAG4FDH-59I?J@DBC6=* 9

Execution times on large data.

Figure 7 shows larger data pattern in the experiment. From the result, both theoriginal and proposed hybrid architectures achieve higher performance comparedwith the centralized orchestration. This indicates that the hybrid architecture issuited for workﬂows having larger data communication between Web services. In
both of small and large data patterns, Figs. 6 and 7 show that the proposed architecture takes slightly shorter execution time compared with that in the original
hybrid architecture.
Figure 8 shows performance result on the number of data. We measured it forﬁve types of the data of which numbers ranging from 1 to 500. In all the cases, theSeptember 4, 2009

8

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoJ. Seo et al.















 








/ "#01, $.*#2 3 4"15

Fig. 8.

!#"%$#&%')(+*-,.*
67$.3 8#3 0#*%29;:<$=3 5

 



>#$.&;?%&<@="15A9;:<$=3 5

Execution times on the number of data.

data size is set to 1M bytes. Figure 8 shows that, the proposed hybrid architecture
achieves higher-performance compared with the other ones when the number ofdata is getting larger due to the reduction of the execution steps in the proposedarchitecture.
The performance at a large number of data is important since there are often
many repetitive operations in bioinformatics workﬂows when they process a large
number of data (such as, data for genes and proteins). The proposed architecture
is suitable for the situation managing such many repetitive operations.
On the other hand, the proposed architecture contains the same overhead ininvoking proxies as the original hybrid architecture. If the data for each operationis small (less than 400k bytes) in its size, the centralized orchestration architecture
gains better performance.
4.2. Experiment with Bioinformatics Web Services in Distributed
Environment
We measured performance for executing a workﬂow composed of bioinformatics
Web services. The Web services we used are getEntry and cpgreport. The getEntry
service receives an entry ID of the DDBJ sequence database [10] and returns thecontent of the entry identiﬁed with the ID. Whereas, the cpgreport service receives
a nucleotide sequence data and returns the locations of CpG-rich regions in thesequence. The service was built by using the EBI Soaplab Web Services [7] for the
EMBOSS programs [13].
For this experiment, we used the following two sets of DDBJ entries. For extracting the above DDBJ entries associated with the GO terms, we used the ARSA

September 4, 2009

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoEﬃcient Execution of Bioinformatics Workﬂows
Table 1.

9

Execution times of bioinformatics Web services

Data set

Data size

Centralized a

Original hybrid a

Proposed hybrid a

Set 1
Set 2

190MB
293MB

410
703

308
638

250
532

Note: a Measured in seconds.

service at the DDBJ Web services. The execution time of the ARSA service is notincluded in the experiment.
• Set 1: 190 DDBJ entries associated with Gene Ontology GO:0007010 (cytoskeleton organization).
• Set 2: 466 DDBJ entries associated with Gene Ontology GO:0016747 (transferase activity, transferring acyl groups other than amino-acyl groups).
The workﬂow invoking the two Web services is carried out with many repetitive
operations. Both services are invoked at the number of the DDBJ entries of theabove sets. The data size of each entry ranges from 1k to 5M bytes.
We placed a workﬂow engine at the National Institute of Informatics, Tokyo, andtwo Web services at the two campuses (Suita and Toyonaka) of Osaka University,
Osaka. In both the original and the proposed hybrid architectures, proxies are placed
one by one at the same local area network of the Web services. The average roundtrip times are 10.1 ms (milliseconds) between Tokyo and Suita, and 1.1 ms between
Suita and Toyonaka. The average ﬁle-transfer speeds measured with FTP are 37
Mbps between Tokyo and Suita, 94 Mbps between Suita and Toyonaka. The engine
and Web services are composed of Linux workstations with Intel Xeon or Core 2
Duo CPUs (2.0GHz or 2.53GHz clock). The Web services were developed in Java,
with the Apache/Tomcat software.
Table 1 shows the execution times of the workﬂow in the distributed environment. “Data size” in Table 1 means the total amount of the output of the getEntry
service. According to Table 1, the proposed hybrid architecture gains better performance than those of the other architectures when a bioinformatics workﬂow to be
executed has many repetitive operations.
5. Discussion
We have proposed a modiﬁcation of the hybrid architecture for workﬂow execution, which is suitable for bioinformatics workﬂows including repetitive invocations.
When the number of data is increased, the advantage of the proposed architectureis also increased.
The data size is important to select the architecture for workﬂow execution.
The experiment results show that the centralized orchestration has advantage if theamount of data to be transferred in a workﬂow is relatively small. If a workﬂow
need to transfer large data between distantly-located Web services to be invoked at

September 4, 2009

10

15:51

WSPC - Proceedings Trim Size: 9.75in x 6.5in

43-SeoJ. Seo et al.

a number of times, our architecture gains better performance.
In this paper, we evaluated only simple repeat patterns of workﬂows. More typesof scientiﬁc workﬂows including conditional branches should be evaluated as future
works. For example, when a workﬂow includes a conditional branch and it need to
select the destination of the data transfer by analyzing the result of a Web service,
the proxy of the Web service cannot simply decide the destination of the transfer.
We will consider the further improvement of the architecture for resolving this issue
in the future.
References[1] Addis, M., Ferris, J., Greenwood, M., Li, P., Marvin, D., Oinn T., and Wipat, A.,
Experiences with e-Science workﬂow speciﬁcation and enactment in bioinformatics,
Proc. UK e-Science All Hands Meeting, 459–466, 2003.
[2] Baker, A., Weissman, J., and Hemert, J., Eliminating the middleman: peer-to-peer
dataﬂow, Proc. 17th Intl Symp. High Performance Distributed Computing, 55–64,
2008.
[3] de Knikker, R., Guo, Y., Jin-long L., Kwan, A. K. H., Yip, K. Y., Cheung, D. W.,
and Cheung, K.-H., A web services choreography scenario for interoperating bioinformatics applications, BMC Bioinformatics, 5(25), 2004.
[4] Kavantzas, N., et al., Web services Choreography Description Language (WS-CDL)
Version 1.0, 2005.
[5] Lbabarga, A., Valentin, F., Anderson, M., and Lopez, R., Web services at the European Bioinformatics Institute, Nucleic Acids Research, 35:6–11, 2007.
[6] Oinn, T., et al., Taverna: a tool for the composition and enactment of bioinformatics
workﬂows, Bioinformatics, 20:3045–3054, 2004.
[7] Senger M., Rice P., Bleasby A., and Uludag M., Soaplab: open source web services framework for bioinformatics programs, Proc. 10th Annual Bioinformatics Open
Source Conf., 2009.
[8] Taylor, I., Shields, M., Wang, I., and Philp, R., Distributed P2P computing within
Triana: a galaxy visualization test case, Proc. IPDPS 2003, 16–27, 2003.
[9] http://www.ebi.ac.uk/Tools/webservices/[10] http://www.xml.nig.ac.jp/index.html[11] http://www.genome.jp/kegg/soap/[12] http://www.uniprot.org/help/uniprotkb[13] http://emboss.sourceforge.net/