Yérom-David Bromberg
email: david.bromberg@labri.fr

Paul Grace
email: p.grace@lancaster.ac.uk

Laurent Réveillère
email: laurent.reveillere@labri.fr

Gordon Blair
email: gordon@comp.lancs.ac.uk

Bridging the Interoperability Gap: Overcoming Combined Application and Middleware Heterogeneity

Keywords: Application, Middleware, Interoperability, Evolution, Domain Specific Languages, Automata

Interoperability remains a significant challenge in today's distributed systems; it is necessary to quickly compose and connect (often at runtime) previously developed and deployed systems in order to build more complex systems of systems. However, such systems are characterized by heterogeneity at both the application and middleware-level, where application differences are seen in terms of incompatible interface signatures and data content, and at the middleware level in terms of heterogeneous communication protocols. Consider a Flickr client implemented upon the XML-RPC protocol being composed with Picasa's Service; here, the Flickr and Picasa APIs differ significantly, and the underlying communication protocols are different. A number of ad-hoc solutions exist to resolve differences at either distinct level, e.g., data translation technologies, service choreography tools, or protocol bridges; however, we argue that middleware solutions to interoperability should support developers in addressing these challenges using a unified framework. For this purpose we present the Starlink framework, which allows an interoperability solution to be specified using domain specific languages that are then used to generate the necessary executable software to enable runtime interoperability. We demonstrate the effectiveness of Starlink using an application case-study and show that it successfully resolves combined application and middleware heterogeneity.

Introduction

Nowadays, complex distributed systems are composed from systems that are developed independently of one another (including legacy systems). This composition occurs either statically, or at runtime as in the case of spontaneous interactions between mobile and pervasive systems. However, existing systems are highly heterogeneous in their interaction methods making such composition challenging.

Applications and systems are developed using a multitude of incompatible middleware abstractions and protocols. For example, remote procedure call protocols such as SOAP and IIOP differ in message content, message format, and addressing meaning that they cannot directly interoperate. The range of incompatible protocols drastically limits interoperability, and thus the practical benefit of systems composition. Protocol standardization should address this issue but has been demonstrably ineffective in practice. Indeed, new competing protocols are frequently introduced to cope with the emergence of new application domains (e.g. sensors, ad-hoc networks, Grid Computing, Cloud Computing, etc.), whereas standardization is slow to complete in comparison.

Interoperability is the ability of one or more systems to exchange and understand each other's data. However, there can be significant mismatches between the interfaces of various systems that provide similar application functionalities, making interoperation impossible. Indeed, developers often implement similar application functionalities in different ways, resulting in incompatible operation signatures and data types. In addition, the behavior of the interfaces may also differ, e.g. a single operation in one case may correspond to a sequence of operations in another.

Existing solutions to these interoperability challenges have generally made assumptions about one another, e.g. that the application is fixed and the protocol heterogeneity must be resolved, or the protocol is common and application differences must be addressed. The former is the view of middleware-based solutions such as protocol bridges [START_REF]Soap2corba and corba2soap[END_REF], Enterprise Service Buses, and interoperable middleware [START_REF] Bromberg | Indiss: Interoperable discovery system for networked services[END_REF] [7] [START_REF] Nakazawa | A bridging framework for universal interoperability in pervasive systems[END_REF]. However, none of these solutions work when there is a difference in application functionalities. For example, in a protocol bridge even a simple difference in the operation name breaks the solution. Service Choreography and Workflow execution languages and tools underpinned by Business Processing Execution Language (BPEL) offer methods to overcome application differences but commonly assume an underlying service platform and description language, e.g. SOAP and WSDL. As a consequence, these approaches are not fit for purpose when applications rely on different middleware. Overall, there is no consistent view of how to tackle problems where both application and middleware heterogeneity is encountered in combination. This leads to the use of solutions involving ad-hoc integration of a number of different technologies.

Due to the potential differences in both middleware protocols and application behavior, a single universal bridge can not be developed to address the heterogeneity issue. Instead, a mediated solution is required in each specific case. Many protocol and application specific mediators are thus required to cover the broad solution space. Nevertheless, such a mediator needs to be dynamically generated to manage the runtime composition of services, because developing this mediator for each particular case can be a challenge for many application programmers. To address this issue, we argue that a domain-specific modelling approach can be used for describing application and protocol specificities. This paper proposes the following contributions towards reaching this goal:

-Application and protocol models. We use automata to model application behaviour where a transition represents the application action and associated input and output data. Similarly, we use automata to model middleware protocols where a transition represents either a sent or received message. -Application-Middleware Mediators. A merged automaton models the merge of two application automata, i.e., this states how the application states from one system are merged with the states of the other heterogeneous system. This mediator model is then used to generate a concrete applicationmiddleware mediator that binds application transitions to physical middleware protocol messages. -An Interoperability Framework. We have implemented a middleware framework to support the generation and execution of mediators. The Starlink Framework [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF] interprets a concrete merged automaton to enable dynamic interoperability at both the application and protocol level. In previous work we have described how Starlink is used to achieve middleware protocol interoperability; here we expand on the approach to achieve combined application and middleware interoperability.

The remainder of the paper is structured as follows. Section 2 presents a motivating case study to highlight the interoperability challenges. In Section 3, we introduce the application and protocol models. Subsequently, in Section 4 we describe how the interoperability framework realizes and executes these models. Our case-study based evaluation is presented in Section 5 and an analysis of related work is provided in Section 6. Finally, we draw conclusions in Section 7.

Motivation: Flickr and Picasa Case Study

To highlight the problem of combined application and middleware heterogeneity we examine the Flickr and Picasa API services, highlight the interoperability challenges and then identify the requirements to overcome them.

Observing Application and Middleware Heterogeneity

Flickr and Picasa are both Web based services that provide similar application functionality. They allow client applications to view, search, add, edit and delete photographs. In addition, they both allow comments to be added to individual photos or sets of photographs. Although they offer similar services, clients of both can not be composed with the services of the other. In practice, interoperability between the two is hindered due to the heterogeneity at both the application level and at the protocol level.

Application Heterogeneity. The APIs of Flickr3 and Picassa4 are large and complex (Flickr has over 100 operations available); hence we concentrate on a small subset of the behavior available. Fig. 1 Flickr and Picasa offer a set of operations for performing similar application requirements; namely, performing a keyword search on publicly searchable photos, listing the comments that have been added to a particular photo result and then finally adding a comment to that same photograph. From these APIs it is clear that application heterogeneity exists in the following two distinct ways:

1. The interface signatures contain sets of operations that differ in operation name, and the types of input and output data of the operation. Consider the operation to perform a general keyword search of public photographs.

The Flickr API provides the search operation with a number of parameters including the optional text parameter for the keyword and page and per page parameters to restrict the returned results; alternatively, Picassa provides a search operation with input parameters: q for the keyword and max-results to restrict the results (n.b. the GET syntax is also shown). 2. The application behavior is captured in different behavior sequences. The Flickr search operation returns a set of identifiers. The getInfo operation should then be called to obtain more information about the photo, including the URL of the jpeg. Alternatively, the Picasa search operation returns the information about the photograph directly in the search results.

Middleware Heterogeneity. The Flickr and Picassa APIs also differ in the protocols they use to access the services. Picassa provides only a RESTful implementation atop HTTP with the Google Data API as an associated data model, whereas Flickr relies either on REST, SOAP, or XML-RPC. A Flickr client (e.g. a smartphone application) implemented using either SOAP or XML-RPC cannot interoperate with Picasa due to the protocol heterogeneity.

Interoperability Requirements

Heterogeneous systems that have been developed independent to one another can not interoperate. To address this issue, mediators need to be created and deployed in the network, so as to provide dynamic composition of existing systems. However, the development of such mediators must consider the following factors:

-The extreme heterogeneity in applications and middleware suggests ad-hoc, manually coded solutions will lead to significant development costs and consumption of computational resources due to the continuous redevelopment of equivalent solutions. -When a new middleware protocol emerges, the API of a service may be migrated to it. Therefore, both existing clients and interoperability mediators for this service would no longer operate correctly. -Similarly, when a new version of an API is released, any changes to the syntax or behavior of the API may mean that the existing clients or interoperability mediators that rely on this API no longer function.

As a consequence, to overcome the combined application and middleware heterogeneity, we propose two key requirements. First, mediators that act as interoperability enablers must be automatically generated and dynamically deployed. Second, middleware protocol migration and API evolutions must be handled with minimal development effort. In [START_REF] Vinoski | It's just a mapping problem [computer application adaptation[END_REF], Vinoski argues that interoperability is a mapping problem and that diversity and heterogeneity should be embraced rather than attempt to homogenize distributed systems. Therefore, developers should be supported in creating these mappings. Hence, in this paper we first propose a high-level, model-based specification of the application differences (independent of any middleware protocol); we subsequently propose that this be used to generate the concrete mediator by binding the solution to particular protocol-to-protocol use cases. For example, an application model of the differences between Flickr and Picasa generates an XML-RPC to REST application-specific mediator or a SOAP to REST application-specific mediator.

Models

Modern software development trends imply that developers implement applications through the use of reusable API operations, that, in a distributed environment, are remotely invoked through the use of an underlying middleware. For instance, Flickr, Picasa, Bing and/or Google maps API define a set of remote operations that can be invoked with different kind of middleware. The way operations are combined together by developers to perform a particular task depends on particular constraints related to the APIs used, and consequently defines an API usage protocol. Inherently, applications performing similar functionalities (i.e. semantically equivalent) but implemented with different APIs, behave differently, and thus have a different API usage protocol. Providing interoperability among applications based on heterogeneous APIs requires first to capture formally their respective APIs usage protocol in order to reason about their behavior.

APIs usage protocol

An API usage protocol S defines sequences of ordered operation invocations. Signatures of invoked operations are expressed in terms of input and/or output messages, more precisely in terms of messages exchanged (as developers of Web Services are used to). Syntactical description of message data fields, including their data types are formalized through the use of abstract messages. An abstract message consists of a set of fields, either primitive or structured [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF]. The former is composed of: (i) a label naming the field, (ii) a type describing the type of the data content, (iii) a length defining the length in bits of the field, and (iv) the value, i.e., the content of the field. A structured field is composed of multiple primitive fields. Hence, we abstract an operation invocation request, noted rvalue operation(arg 1 ...arg n ), as two abstract messages. First, an abstract message named operation that is sent and which is composed of a set of n fields such as f ield 1 = arg 1 , ..., f ield n = arg n . Second, an abstract message named rvalue that is received. We note msg f ield the operation that selects the field f ield from the abstract message msg.

As a result, a sequence of operation invocations S describing an API usage protocol is formalized as an automaton A S with edges labeled with abstract messages sent or received according to the signature of remote operations invoked. More formally, A S is defined as a 6-tuple such as A S = (Q, M, q 0 , F, Act, →) with Q a finite set of states, M a finite set of both incoming or outgoing abstract messages, q 0 ∈ Q the starting state and F ⊂ Q a set of accepting states. Act = {?, !} defines two kinds of actions: ! to invoke a remote operation and ? to receive a reply from a previously invoked remote operation.

Hence, the transition relation, noted →⊆ Q × Act × M × Q, can be either an invoke-transition or a receive-transition. The former is noted s 1 !operation -------→ s 2 for (s 1 , !, operation, s 2 ) ∈→ and indicates the next state to which the automaton passes as soon as the operation operation is invoked. The latter has the following form s 1 ?rvalue -----→ s 2 for (s 1 , ?, rvalue, s 2 ) ∈→ and changes the state of the automaton from s 1 to s 2 once the invocation reply rvalue is received. As a result, A S acts as a call graph of invoked operations and specifies the order in which they should be invoked.

For instance, Fig. 2 demonstrates the Picasa and Flickr API usage protocols that developers might follow to implement either a Picasa or a Flickr application with similar functionalities.

API usage Protocol mismatches

From an application perspective, two applications, A 1 and A 2 , which follow respectively an API usage protocol A S 1 , and an API usage protocol A S 2 , may interact seamlessly with each other if and only if there is a way to intertwine their respective API usage protocols. Performing this kind of merging assumes to resolve different kinds of mismatches. As we express operation invocations in terms of messages exchanged, we can leverage on guidelines of possible mismatches that have already been identified for developing Web services adapters [START_REF] Kongdenfha | Mismatch patterns and adaptation aspects: A foundation for rapid development of web service adapters[END_REF] and apply them to API usage protocol mismatches. For instance, the comparison of two API usage protocols such as A F lickr and A P icasa , depicted in Fig. 2, enables us to point out the different mismatches that occur:

Ordering mismatch. When applications invoke similar remote operations in a different order, an ordering mismatch may occur. For instance, according to A P icasa , a Flickr developer should invoke a getPhotoUrl operation right after a photoSearch. However, the getPhotoUrl operation is called, in fact, later in the call graph.

Extra or missing message mismatch. If one application invokes a remote operation that another application never invokes, there is an extra or missing message mismatch. For instance, a Picasa developer does not invoke any operations similar to the Flickr operation getInfo, which is specific to the Flickr API.

One-to-many mismatch. An API can perform a particular task with only one remote operation, whereas another API may require several operations to do a similar task. For instance, obtaining a photo URL requires only one search operation using Picasa, whereas it requires two operations (i.e. search and getInfo) with Flickr.

In the context of an API usage protocol, the aforementioned mismatches emerge as soon as there are mismatches among operations at their signature level. As a result, there is not always a one-to-one mapping between messages. Note that resolving API usage protocol heterogeneity is theoretically similar to resolving heterogeneity at the protocol layer but acts on messages that abstract operation invocations instead of network messages. So resolving operation signatures mismatches leads us to reason about semantic equivalence among the abstract messages exchanged. To this end, we extend our model with a semantic equivalence operator ∼ = that acts on messages, abstracting operations, as defined below.

(A S ) × Act× - → m×States(A S ) with Act = {!, ?} and - → m = {m i , ..., m k , ..., m n } ∈ M sg (A S ) with (i, k, n) ∈ {1, .., n}. Thus, s 1 ! - → m = ⇒ s 2 (resp. s 1 ? - → m = = ⇒ s 2 )
gives the sequence of abstract messages sent (resp. received) from the state s 1 to s 2 . Definition 5. Let the intertwining operator such as !s i .method 1 !s j .method 2 is true iff ∃s 0 ∈ I(A S 1 ).∃s i ∈ States(A S 1 ).∃s j ∈ States(A S 2 ).

∃method 1 ∈ M sg (A S1 ).∃method 2 ∈ M sg (A S2 )| ((?method 1 ∼ =?method2) ∨ (?method 2 ∼ = (s 0 ? - → m = = ⇒ s i , ?method 1 )) ∧ !s j .method 2 ∼ = (s 0 ? - → m = = ⇒ s i , s 0 ! - → m = ⇒ s i ) Reciprocally, ?s i .method 1 ?s j .method 2 is true iff !s i .method 1 !s j .method 2 .
Thus, if A S 1 has a sequence of n intertwined operations with A S 2 , it means that there exists n transitions, named γ-transitions, that go back and forth between A S 1 and A S 2 without sending or receiving messages but applying successful data transformation on semantically equivalent messages as described in Section 4. As a result, the resulting automaton is said to be a k-colored automaton. The k color enables one to identify states that belong to either A S 1 or A S 2 as depicted in Fig. 3. Further, states linked by a γ-transition are represented by bicolored nodes such as nodes , , , ,, . For instance, at node , Flickr photoSearch invocation can be intertwined with the corresponding Picasa photoSearch as !f lickr.photoSearch ∼ =!picasa.photoSearch, and a γ-transition is taken to move from the Flickr API usage protocol to the Picasa one through some translations on data fields as messages are semantically equivalent. Definition 6. A k-colored automaton is an automaton with all its states colored by a color k. Thus an automaton A S colored by a color k is noted A S k where States(A S k ) = {s k 0 , ..., s k i , ..., s k n }.

Definition 7. An application A 1 may interact with an application A 2 iff their colored API usage protocol A 1 S1 and A 2 S2 are mergeable, and noted A 1

S1 A 2 S2 , such that ∃Seq = {..., (s 1 x , s 2 y ), ...} ⊆ States(A 1 S1 ) × States(A 2 S2 )with(x, y) ∈ {1, ..., n}∧∃(!m 1 , !m 2 ) ⊂ M sg (A 1 S1 )×M sg (A 2 S2 ) | {!s x .m 1 !s y .m 2 } ∃(s i , s j ) ⊂ EN D(A 1 S1 ) × EN D(A 2 S2 ) with (i, j) ∈ {1, ..., n} | s i , s j ∈ EN D (A 1 S1 A 2 S2 ).
Note that all invocation operations from A S 1 can not be always intertwined with the ones of A S 2 , but it does not hinder necessarily the interoperation. Hence, it is required to consider that it is possible to get two different kinds of k-colored automaton: strongly or weakly merged. The former case still arises even if some invocation operations from A S 1 are not intertwined, however their corresponding replies must be semantically equivalent to replies received from A S 2 . Otherwise, if this condition is not satisfied the k-colored automaton is said to be weakly merged. For instance, in Fig. 3, the Flickr operation getInfo has no equivalent in the Picasa API, however, its reply is semantically equivalent to the Picasa photoSearch reply previously received. The flickr getInfo operation can be invoked (i.e through the send and receive of f lickr.getInf o) without both being interleaved and hindering the interoperation. The depicted automaton is still strongly merged. ----→ s j . The operator ∼ = is defined as previously.

Note that a data transformation λ i ∈ {λ} is a function λ i : f ield 1 × ... × f ield n that performs a data transformation and may require as arguments some fields extracted from previously received messages.

Applying the Starlink Framework

Starlink is a runtime middleware framework which provides an engine to dynamically interpret and execute middleware models. The key design principles are based upon the knowledge that middleware technologies are built upon messagebased solutions, i.e., middleware protocols consist of sending to and receiving messages from a network. We have previously documented how the framework [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF] !flickr. photoSearch be used to dynamically generate direct protocol bridges (i.e. connecting middleware protocols of similar types, such as service discovery and RPC). We now describe how it can be used more broadly to develop and deploy applicationmiddleware mediators. We first describe the models used by Starlink and then how they are executed. Subsequently, we describe how the application models introduced in Section 3 are used to generate the Starlink executable models.

Starlink Models

In this section we introduce the core models that are interpreted by Starlink. Firstly, how protocol message sequences are specified. Secondly, how message format is defined. Thirdly, how message translation logic is described.

Message Sequences. The behavior of a protocol is traditionally described by an automaton where transitions represent message exchanges. However, protocols vary in their interaction with the network, in terms of the transport protocol used, whether requests are sent by unicast or by multicast, and whether responses are received synchronously or asynchronously. Starlink uses the previously introduced k-colored automata to capture the properties of a protocol by a color k and ensure that the messages are executed using the appropriate network services [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF]. Fig. 4(a) illustrates the k-colored automaton for general IIOP client behaviour, i.e. a GIOP request message is sent synchronously to an IIOP server and on the same connection it receives the GIOP reply message. Fig. 4(b) illustrates SOAP client behaviour.

Message Format and Content. A network message is organized as a sequence of text lines, or of bits, for a binary protocol, containing both fixed elements and elements specific to a given message. Extracting values from a message represented as a sequence of text or binary characters is unwieldy, and creating messages is even more complex, because the element values may become available at different times, making it difficult to predict the message size and layout. Hence, we have proposed a domain specific language approach to describe messages such that the required message parsers and composers can be generated automatically. The Starlink framework is flexible to allow different types of language to be used to specify message formats; each language can be termed a Message Description Language (MDL). This flexibility better supports the parsing and composing of a wide range of protocols. For example, specialised languages for binary messages, text messages and XML messages can be plugged into the framework. From an MDL specification, Starlink dynamically generates parsers that transform network messages to the abstract message representation. Reciprocally, the generated composers do the reverse. An example of MDL specification for GIOP messages is presented in Fig. 5. Detailed discussion of the language is left from here, and further information is available in [START_REF] Bromberg | Starlink: runtime interoperability between heterogeneous middleware protocols[END_REF].

Message Translations. When several protocols need to interoperate, it is necessary to express the relation among them and to describe the message translation logic (MTL), which defines how to translate messages from one protocol to another. Translation logic is used to describe the translation of data and behaviour where messages are semantically equivalent, i.e. the messages perform similar operations. This logic is executed at the bi-colored states of a colored automata and typically consists of field transformation where a field in the message to be composed is assigned a value from a received field (there will typically be a transformation function as part of this assignment). One key operator of the MTL language is the assignment operation.

The Starlink Framework: dynamically interpreting middleware models

As illustrated in Fig. 6, the Starlink framework interprets the previously described middleware models at runtime in order to support the necessary middleware behaviour on demand. The network engine sends and receives physical messages (i.e. data packets) to and from the network. A transition in the k-colored automata attaches network semantics to describe the requirements of the network. The network engine then provides the services to meet these requirements, which could include different types of transport or multicast behaviour. The current implementation of the network engine provides traditional TCP and UDP services for infrastructure networks. However, the architecture is configurable so that if Starlink were to be deployed in more heterogeneous environments, e.g. ad-hoc networks, this network engine could be replaced with configurable services for ad-hoc routing [START_REF] Ramdhany | Manetkit: supporting the dynamic deployment and reconfiguration of ad-hoc routing protocols[END_REF].

The message parsers read the contents of a network packet and parse them into the AbstractMessage representation such that the data can be manipulated during the mediation process. For example, if a HTTP message is received a HTTP parser reads all the fields of the header and body. Correspondingly, message composers construct the data packet for a particular protocol message, e.g. constructing the content for a HTTP GET message. Importantly, the message composers and parsers are generic reusable software elements that interpret high-level specifications of message content. The Message Description Language (MDL) specification (as described previously) specializes these generic components at runtime to create a specific protocol parser or composer.

The automata engine executes the behaviour of the merged automata, i.e. it controls the sequence of sending, receiving, parsing, composing and translation of messages. In Starlink, there a three types of states: i) a receiving state waits to receive a message and will only follow a matching receive transition when a matching message is received; ii) a sending state sends a message described in the single transition; iii) a no-action state is a translation state that translates data from the fields on one or more of the prior messages into the message to be constructed.

Generating and Executing Application-Middleware Automata

API usage protocol automata are specified independent from particular middleware. We now describe how these are bound to a specific protocol to create a Starlink executable k-colored automaton specific to the API implementation.

As described in Section 3 the API usage protocol automaton defines the application actions in terms of sending actions (invocation) and receiving actions (reply response). These transitions contain the action label and the abstract message that includes the input or output data values. Actions correspond to distributed interactions. However, they cannot be executed because they do not relate to a specific communication protocol. Indeed, the labels and data are only made concrete using protocol messages. Therefore, the API usage automaton must be bound to a concrete protocol automaton in order to be executed. We term the resulting model an application-middleware automaton. To better illustrate this procedure, Fig. 7 shows how a simple API usage protocol automaton is bound to two heterogeneous middleware protocols, namely IIOP and SOAP. The client application performs an addition operation (Add) from a remote service. For this, it sends an Add action, followed by the reception of the Add action response. The input values consist of the x and y integer parameters to be added. The output value is the returned integer parameter z.

To bind to a particular protocol we require: i) the k-colored automaton of the middleware protocol (e.g. Fig. 4(a)), ii) the MDL specification of that protocol's messages (e.g. Fig. 5) and iii) the set of rules that describe how a particular protocol (e.g. GIOP) is bound to the application automata concepts (i.e. the action labels, and the parameters). The rules to bind applications to SOAP in one case and IIOP in the other are illustrated in Fig. 7. IIOP and SOAP are both RPC protocols and hence the actions correspond to the request and response messages of each protocol, as seen by the corresponding k-colored sequence. The action label then binds to specific fields within the message described by MDL: the operation field of the GIOP Request message, and the methodname field of the SOAP request envelope. Similarly, the request action parameters (the x and y integers) relate to the first two parameters in the ParameterArray field of the GIOP Request message. The return value parameter (the z integer value) relates to the first parameter of the GIOP reply ParameterArray. Starlink is then able execute the application-middleware in order to concretely achieve the application behaviour. At receiving states, the automata engine waits for middleware messages of a particular type (e.g. a SOAP Reply) and also with a particular action label (e.g. add). Subsequently, at send states the middleware message (e.g. SOAP request) is constructed placing the appropriate application labels and input values in the identified fields as described by the protocol binding rules.

Generating and Executing the Intertwining API Usage Protocol Automata

A similar binding process is carried out to generate the concrete version of an intertwining API Usage Protocol Automaton, i.e., where two heterogeneous applications are merged. For transitions, the bindings are identical to those explained in section 4.3; the difference occurs at the bi-colored states where MTL rules must be executed to translate application data from a parsed message into the composed message. In this situation we must generate the concrete MTL rules relating to the MTL definitions in the Intertwining automaton.

To illustrate this procedure we continue with the simple addition example. In this case the SOAP service provides an add operation with an int Plus(int, int) signature whereas the IIOP client interface signature is int Add(int, int). Hence, the application difference is in the operation name. Fig. 8 shows how the merged application automaton is bound to the concrete merged automaton. On the left side of the figure is the specified application merge, with the bi-colored states representing the translation of parameters between actions. On the right

Evaluation

To evaluate our approach for overcoming combined application and middleware heterogeneity, we use a case-study based methodology. That is, we apply Starlink to particular use cases and observe the extent to which interoperability is achieved. For this purpose we consider the application scenario described in Section 2. This application performs search and display of public photographs and requires interoperation between independently developed XML-RPC and SOAP Flickr clients and the Picasa Rest implemented API. We hypothesize the following:

1. The Starlink models can specify the application differences between Flickr and Picasa independent of SOAP, XML-RPC and HTTP messages. 2. Concrete models for both the XML-RPC and SOAP use cases can be successfully generated, deployed and executed to achieve the required interoperability with the Picasa API. 3. The use of high-level specifications simplifies the development of mediators and resolves evolution problems.

Flickr-Picasa Case-Study

In this case study we develop and deploy two mediators: a Flickr-Picasa mediator for XML-RPC to Rest, and a Flickr-Picasa mediator for SOAP to Rest. In the first instance we specify the application automata describing the API usage of both the client and service, as shown Fig. 2. Although automata are written using the XML-based Starlink language for k-colored automata, we use visual representations for clarity. Subsequently, we specified: i) the intertwined API usage automaton as shown in Fig. 3, ii) the SOAP protocol models consisting of the MDL and the k-colored protocol automaton, iii) the XML-RPC models, and iv) the Rest models. The next step consists of generating the application-middleware mediators by binding the single intertwined automaton to the two particular use cases. We now present in the remainder of this section the results of this binding. For sake of clarity, we only describe subsets of it to highlight key results. An extract of the binding of the intertwined Flickr and Picasa search operations to an 'XML-RPC to Rest' concrete mediator is shown in Fig. 9. It illustrates how the XML-RPC Flickr message is parsed to extract the application information from transition S 1 to S 2 (e.g. the action label flickr.photos.search and the data parameter labelled text). The MTL for S 2 to S 3 then describes how the fields are translated before constructing the HTTP message to perform a Picasa search. The subsequent translation of the responses, from state S 5 to S 6 , highlights a case where further functionality is required. The values that must be returned to the Flickr search operation is a list of Flickr photo identifiers in the format <photo id id='1111' owner='1111111@NO1'>. To handle this mapping, the bridge creates a cache of dummy identifiers for each photo result returned in the Picasa action response (the <entry><id> value from the XML data). The MTL provides a keyword operation cache that caches data values for arbitrary data identifiers.

An example of operation mismatch in the intertwined automaton is illustrated in Fig. 10. Indeed, when the Flickr client sends a getInfo action request, there is no corresponding operation in Picasa because the required action result data has already been received in Picasa's search response. Hence, when the getInfo message is received at S 8 then a data translation is performed: the photo id parameter is used to extract the Picasa <entry> value from the cache using the getcache MTL keyword. The Flickr <photo> structure is then filled using the corresponding tags from the Picasa <entry> structure.

The binding of the intertwined Flickr and Picasa comment operations to a 'SOAP to Rest' concrete mediator is similar to the XML-RPC binding and uses the rules provided in section 4. In this case, the generated MTL and k-colored automata refer to SOAP message content rather than XML-RPC.

Finally, we hand developed two test standalone client applications in SOAP and XML-RPC that searched and displayed photographs from the Flickr API. We then deployed Starlink in the network and loaded the concrete models. When executed, both clients were able to search and view photographs from the Picasa API. For our experiments, we deployed a simple proxy to redirect the Flickr requests (originally directed to the Flickr servers) to the local Starlink mediator.

Analysis

The automaton that specifies the application model contains no reference to a concrete protocol, message format or network semantics. As a consequence, it is seen that the first hypothesis that application behaviour can be modelled independent of middleware is successfully achieved. The generated concrete mediators, when deployed in the network, successfully parse and compose middleware messages and bridge the heterogeneous application behaviour in both the XML-RPC and SOAP case. Hence, the hypothesis that such code can be generated for multiple specific protocols is shown to be true. Finally, it can be argued that the definition of a single application model simplifies the development of interoperability solutions. There is no need to hand code each use case, and it is similarly straightforward to handle API migrations or changes using only the models.

Related Work

Middleware solutions to interoperability generally focus on bridging the gap between the various middleware technologies involved. These assume a common application standard, i.e., that applications wishing to interoperate use the same interface defined in the same language (e.g. Interface Description Language (IDL) or Web Services Description Language (WSDL)). In this situation the interoperability gap is between heterogeneous middleware protocols. Protocol bridges [START_REF]Soap2corba and corba2soap[END_REF], Enterprise Service Buses [START_REF] Iona | Artix esb[END_REF][START_REF]Websphere message[END_REF], and Interoperability Frameworks e.g. WSIF [START_REF] Duftler | Web services invocation framework (wsif)[END_REF], uMiddle [START_REF] Nakazawa | A bridging framework for universal interoperability in pervasive systems[END_REF], OSDA [START_REF] Limam | Osda: Open service discovery architecture for efficient cross-domain service provisioning[END_REF], and UIC [START_REF] Roman | Reflective middleware: From your desk to your hand[END_REF] are well known solutions to this problem. However, because they do not consider heterogeneity at the application-level they are not suited to the composition of complex systems-of-systems; where independently developed applications are composed dynamically it is unlikely that the application interface has been agreed in advance.

Several technologies are available to manage the differences between application service interfaces in terms of operation and message sequences. As an example, Web Services orchestration and choreography methods [START_REF] Peltz | Web services orchestration and choreography[END_REF] provide languages such as Web Services-Choreography Description Language (WS-CDL) and Business Process Execution Language (BPEL) to handle such translations. These languages are similar to Starlink in that they provide high-level constructs to mediate behaviour sequences and also perform data translations. However, they assume an underlying platform (e.g. Web Services) and focus on choreography rather than on direct interoperability. As a consequence, differences in underlying protocols cannot be handled. Furthermore, they cannot manage the differences in interface languages. For example, BPEL cannot be used to generate a solution to make a CORBA IDL-based client interoperate with a SOAP WSDL-based service.

Model Driven Architecture (MDA) [START_REF]Object Management Group. Model driven architecture (mda)[END_REF] proposes a similar methodology to Starlink, which indeed is inspired by the modelling ideas put forward by MDA. Application systems are specified using an abstract model, called the Process Independent Model (PIM). The PIM is deployed atop middleware based platforms described by the Platform Specific Model (PSM). Bridges are then deployed where there are exchanges between different PSMs to ensure that the platform heterogeneity is resolved. However, MDA is characterised by ad-hoc solutions with limited support for the generation of bridges between the platform models.

Formal specifications have been proposed to generate mediators between heterogeneous systems. Yellin and Strom [START_REF] Yellin | Protocol specifications and component adaptors[END_REF] describe a method to enhance application interfaces with sequencing constraints in addition to rules that describe how the application data can be bridged. This information is then used to generate the code of the software adapters. Similarly, [START_REF] Kumar | A discrete event systems approach for protocol conversion[END_REF] describes a discrete event systems method for describing a converter between disparate protocols. While closely related to our formal models of protocol and translation, our approach further investigates the concrete realities of application differences based upon heterogeneous middleware paradigms and message formats.

Currently Starlink developers construct the merged automata; however, emerging solutions have investigated how to generate the mediator automatically. [START_REF] Spalazzese | Towards a formalization of mediating connectors for on the fly interoperability[END_REF] models protocols as labelled transition systems (LTS) and presents an algorithm to identify the merge of the two; however at present it considers only message sequence differences not data heterogeneity. Similarly, work in the CONTESSA project [START_REF] Gutierrez | A reflective middleware framework for communication in dynamic environments[END_REF] presents a reflective approach to compose heterogneous protocol-based services. This utilises semantic models of the transitions between the configurations of the protocols and services. While this doesn't cover the complete interoperability mappings that Starlink proposes it does offer important insights into how reasoning and composition can be performed automatically at runtime.

Conclusions

In this paper we have shown that the interoperability problem is characterised by differences in both application APIs and middleware protocols. Existing solutions have focused on one of these dimension while making assumptions about the common nature of the other. In complex and dynamic systems such assumptions are invalid, and new approaches are required to consider application and middleware together. For this purpose, we have presented Starlink5 -a framework to model applications and protocols such that the code to interoperate can be generated. Specifically, this consists of application and application-middleware mediator models (specified using automata and domain specific languages) that are interpreted at runtime. We have performed evaluation of Starlink using a case study involving heterogeneous web-based services (i.e. photo sharing). Preliminary results show that Starlink can successfully address the interoperability challenges, and simplify the task of connecting disparate systems.

Starlink requires the developer to write models, however given the scale of heterogeneous applications and protocols automated generation of these models is the ultimate goal. Hence, it is necessary to reason about the individual application and protocol models and generate the merged automata between. To underpin this reasoning we believe that additional semantic models can be used to infer the translation logic and we are investigating the use of ontologies [START_REF] Daconta | The Semantic Web: A Guide to the Future of XML, Web Services and Knowledge Management[END_REF] and their associated tools. For full automation, machine learning is required and hence we are also investigating learning techniques to understand and model the behaviour of the individual protocols. For example, dynamic binary analysis approaches have been used to identify the field structure of network messages [START_REF] Caballero | Polyglot: automatic extraction of protocol message format using dynamic binary analysis[END_REF] and learning algorithms have been utilised to learn the interaction behaviour of application and middleware protocols [START_REF] Howar | On handling data in automata learning -considerations from the connect perspective[END_REF].

Fig. 1 .

 1 Fig. 1. Highlighting the Flickr and Picasa APIs

Definition 8 . 1 S1 A 2

 812 The resulting A S2 is a k-colored automaton, with k = {1, 2}, defined as a 7-tuple (Q, M, q0, F, Act, →, γ -→, P, ∼ =) where Q = k=1...2 States(A k Sk ), M = k=1...2 M sg (A k Sk ), q 0 a starting state ∈ I(A 1 S1 ), F = k=1...2 EN D(A k Sk ), P = {λ} a set of data transformations on messages semantically equivalent according to the ∼ = relation, and →= k=1...2 T (A k Sk ). Finally, γ -→⊆ States(A 1 S1 ) × P × States(A 2 S2 ) are γ-transitions that occur when sent (or received messages) from States(A 1 S1 ) can be interleaved with the ones from States(A 2 S2 ) according to the operator. γ-transitions take the form s i γ({λ})

Fig. 3 .

 3 Fig. 3. Merged Flickr and Picasa usage protocol API

Fig. 4 .Fig. 5 .

 45 Fig. 4. Examples of concrete k-colored automata

Fig. 6 .

 6 Fig. 6. Architecture of the Starlink framework

  GIOP Request operation !Action = GIOP Reply RequestID Data Rules P arameterN = GIOP Request P arameterArray P arameterN P arameterN = GIOP Reply P arameterArray P arameterN Action Rules !Action = SOAP Request M ethodN ame ?Action = SOAP Reply M ethodN ame Data Rules P arameterN = SOAP Request P arameterArray P arameterN P arameterN = SOAP Reply P arameterArray P arameterN

Fig. 7 .

 7 Fig. 7. Binding to concrete application-middleware automata

!Fig. 8 .

 8 Fig. 8. Construct a concrete merged application automaton

Fig. 9 .

 9 Fig. 9. XML-RPC to Rest binding for Search operation

! 7 S 8 S 9 ?

 789 XML-RPC MethodCall (flickr.photos.getInfo, photo_id) S XML-RPC MethodResponse (flickr.photos.getInfo, <photo>) Entry = getCache( S 8 .M ethodCall P arams.param1) Photo.title = Entry.title Photo.urls.url = Entry.Content ... S 8 .M ethodResponse P arams.param 1 = P hoto

Fig. 10 .

 10 Fig. 10. MTL translation for Flickr-Picasa mismatch behaviour

  illustrates how the APIs of flickr.photos.search(api_key, tags, text, per_page, page, ...) flickr.photos.getInfo(api_key, photo_id) flickr.photos.comments.getList(api_key, photo_id, min_comment_date, max_comment_date) flickr.photos.comments.addComment(api_key, photo_id, comment_text)

	PicasaBaseURL -https://picasaweb.google.com/data/feed/api
	photos.search(q, max-results)	[GET PicasaBaseURL/all?q=tree&max-results=3]
	getComments(kind)	[GET PhotoURL?kind=comment]
	addComment(entry) [POST PhotoURL, <entry> </entry>]

  Informally, application A 1 may interact with application A 2 if the following conditions are satisfied: (i) their respective API usage protocols A S 1 and A S 2 share a sufficient number of similar operations that enables them to have a successful sequence of operations to reach their respective final state, (ii) the identified semantically equivalent can be intertwined together,i.e. invoked in an alternate order when required. In other terms, invoked operations, i.e. request messages, from A 1 must be sequentially translated into a semantically equivalent request message followed by a corresponding reply message from A 2 . Based on the previous introduced definition, we extend the model with a history and an intertwining operator to formally define the aforementioned constraints.

	3.3 k-Colored Automata: Intertwining API usage Protocol

Definition 1. Let -→ m a sequence of abstract messages. Further, !m or ?m denotes a message to be sent or received, and !s i .m or ?s i .m denotes a message sent or received in a specific state s i . Definition 2. Let ∼ = a semantic equivalence operator such that n ∼ = -→ m is true if and only if for every mandatory field of n, noted M f ields (n), there exists a semantically equivalent field in one message of the sequence -→ m. So n ∼ = -→ m if and only if ∀n f ield ∈ M f ields (n), ∃m ∈ -→ m = m 1 . . . m n such as n f ield |= m f ield. Definition 3. Let I(A S ) the set of initial states and EN D(A S ) the set of final states of A S . The set of all states of A S is States(A S ) = I(A S ) ∪ EN D(A S ). Further, let M sg (A S ) the set of all messages and T (A S ) the set of all transitions of A S . Definition 4. Let ⇒ the history operator defined such as ⇒⊆ States

http://www.flickr.com/services/api/

http://code.google.com/apis/picasaweb/

the framework is available to download at http://starlink.sourceforge.net

Acknowledgments.

Part-funded unded under the EU FP7 Connect project (http://connect-forever.eu).


Vitold E Galkin

Albina Orlova

Olga Cherepanova

Marie-Christine Lebart

Edward H Egelman
email: egelman@virginia.edu

High-resolution cryo-EM structure of the F-actin-fimbrin/plastin ABD2 complex

Many actin binding proteins have a modular architecture, and calponin-homology (CH) domains are one such structurally conserved module found in numerous proteins that interact with F-actin. The manner in which CH-domains bind F-actin has been controversial. Using cryo-EM and a single-particle approach to helical reconstruction, we have generated 12-Å-resolution maps of F-actin alone and F-actin decorated with a fragment of human fimbrin (L-plastin) containing tandem CH-domains. The high resolution allows an unambiguous fit of the crystal structure of fimbrin into the map. The interaction between fimbrin ABD2 (actin binding domain 2) and F-actin is different from any interaction previously observed or proposed for tandem CH-domain proteins, showing that the structural conservation of the CH-domains does not lead to a conserved mode of interaction with F-actin. Both the stapling of adjacent actin protomers and the additional closure of the nucleotide binding cleft in F-actin when the fimbrin fragment binds may explain how fimbrin can stabilize actin filaments. A mechanism is proposed where ABD1 of fimbrin becomes activated for binding a second actin filament after ABD2 is bound to a first filament, and this can explain how mutations of residues buried in the interface between ABD2 and ABD1 can rescue temperaturesensitive defects in actin.

cytoskeleton ͉ electron microscopy ͉ helical polymers A lmost a dozen proteins involved in cell signaling and cy- toskeletal structure have been shown to contain structurally conserved calponin-homology (CH) domains (1). Based on this structural conservation, it has been suggested that many actin binding proteins containing CH-domains interact with F-actin in a similar way (2)(3)(4). Fimbrin (called plastin in humans) is involved in actin bundle formation in microvilli and stereocilia, and is composed of two actin binding domains (ABD1 and ABD2), each containing tandem CH-domains. A model of actin-fimbrin bundles (5) assumed that ABD2 interacts with actin filaments in the same manner observed for ABD1 (2). Alternatively, we have previously suggested that CH-containing proteins bind to F-actin polymorphically (6). Biochemical studies suggested that ABD1 and ABD2 of plastin interact with actin in different manners (7). We have also shown that the CH-domain within the eponymous protein of this family, calponin, does not actually contact actin when calponin is bound to F-actin (8).

It has been observed that interactions of many actin binding proteins with actin filaments are highly cooperative and involve structural transitions that propagate along the actin filament (9,10). The uniform arrays seen in fimbrin-F-actin sheets (5) suggest that there are cooperative mechanisms that dictate how cross-bridging occurs simultaneously with polymerization. Structural changes in actin upon binding of ABD1 to F-actin (11) have been observed and were suggested to explain this cooperativity (5). To evaluate the structural changes in F-actin induced by the binding of fimbrin ABD2, we need to have a high-resolution model for the structure of F-actin alone.

Our understanding of F-actin structure has been hampered by the fact that F-actin cannot be crystallized, given that the symmetry of the filament is incompatible with any crystal symmetry. Studies using EM have been plagued by the fact that the helical symmetry of F-actin is not fixed but allows for a large variability in the angle between adjacent subunits (12). A high-resolution reconstruction of a tightly cross-linked bundle of actin filaments (13) has confirmed the variability in twist as well as tilt (14) of subunits seen for free actin filaments, but every actin subunit in this bundle is bound by an additional protein. X-ray fiber diffraction from oriented gels of F-actin has been used with success (15), but the variable twist of F-actin and the model-building approach needed result in solutions that are not necessarily unique at higher resolution (16).

The single-particle approach, iterative helical real space reconstruction (IHRSR), to electron microscopic threedimensional reconstruction of helical structures having intrinsic disorder (such as F-actin and RecA) (17) allows us to sort the short segments extracted from such filaments into relatively homogeneous classes. As classes become more homogeneous, they can be reconstructed at higher resolution. In contrast, the heterogeneity in such filaments means that techniques that average over long lengths will suffer from poor resolution. In addition to the twist disorder (12), F-actin possesses structural polymorphism. One form of polymorphism involves tilted subunits that also undergo a substantial opening of the nucleotide binding cleft (14). One of the most variable parts of actin among different crystal structures is subdomain-2 (SD2), and within F-actin, SD2 can be largely disordered (18). We have therefore used a single-particle approach to reconstruct both pure F-actin filaments as well as F-actin filaments decorated with ABD2 of fimbrin. We have achieved an unprecedented resolution for reconstruction of both filaments by using cryo-EM of unstained samples and by image processing to overcome the structural heterogeneity.

Results

Pure F-Actin Reconstruction. As a control for understanding the complex of ABD2 with F-actin, we have polymerized and imaged pure F-actin under similar conditions to those used for the complex. We found a substantial heterogeneity within such pure actin filaments. In addition to the variable twist (12,13), F-actin shows other structural heterogeneity. Starting with 28,134 filament segments (each Ϸ480 Å long) obtained from cryo-EM images (Fig. 1a), we found similar conformational states of F-actin in the frozen-hydrated filaments as had previously been found by using negative stain: Ϸ31% of segments had subdomain-2 (SD2) disordered (19) (and thus density for this region was missing in the reconstruction), and Ϸ28% were found in the ''tilted'' state (14). The largest class (41%) was the ''canonical'' state, and this class was reconstructed separately (Fig. 1c).

The resolution was determined to be 12.5 Å by using a conservative measure [see supporting information (SI) Fig. 4 and Methods]. The best measure of resolution, however, is the quality of the map itself, and an atomic model of the actin filament filtered to 12 Å is almost indistinguishable from the reconstruction (Fig. 1d). The resolution in our reconstruction is not homogeneous, and this reflects different degrees of disorder in different parts of the actin protomer within the filament. Some parts of the map have better than 12 Å resolution, as can be seen by the helix followed by a loop in actin's SD4 (residues 221-237), which is resolved at 10 Å resolution (SI Fig. 4c).

Actin protomers possess a relatively closed ATP binding cleft in the reconstruction; thus, a crystal structure of G-actin with a closed cleft was used for atomic modeling (20). When the actin subdomains were fit separately (Fig. 1), only small perturbations from the original crystal structure (Ϸ2 Å rmsd) were required to generate a better fit. The conformation of the protomers in our atomic model of the ''canonical'' state of F-actin is closer to the original model proposed by Holmes and colleagues (15) (rmsd of Ϸ2.7 Å) than to a refined model (21) (rmsd of Ϸ2.9 Å). However, because we observe a multiplicity of structural states in F-actin, an atomic model of each structural state will need to be generated, and we are not suggesting that there is one atomic model of the actin filament.

Actin-ABD2 Reconstruction. Using similar methods, we have been able to generate a three-dimensional reconstruction of F-actin decorated with ABD2 of human fimbrin (L-plastin) at 12-Å resolution (Fig. 2a). Analysis of the twist distribution within these decorated filaments shows that the binding of ABD2 reduces the variability in twist found in naked F-actin (data not shown). The ABD2 fragment that we have used contains the tandem CH3 and CH4 domains (7). The decoration of F-actin is very clear in the original images (Fig. 1b), because ABD2 produces ''chevrons'' on F-actin that are somewhat reminiscent of myosin S1 decoration of actin. The reconstruction clearly displays these chevrons projecting out from F-actin at an angle of Ϸ45°. At this resolution, the asymmetry between the two CH-domains within ABD2 is great enough that they can be 17), using a subset (n ϭ 10,986) of the total segments collected after sorting to exclude structural variability, such as tilted actin and segments where subdomain 2 was disordered. Actin subdomains are labeled with red numbers. To improve the fitting, the actin monomer was divided into three parts: SD1 (residues 2-33, 70 -145, and 336 -375), SD2 (34 -69), and SD34 (146 -335). These parts were fit as rigid bodies, and the corresponding symmetry was imposed to build a model filament (c, blue ribbons). To evaluate the similarity between the model and the actual reconstruction, the atomic model was filtered to 12 Å (d, transparent surface) so that it may be compared with the original volume (c, transparent surface). Our model is in agreement with the contacts between the protomers in the Holmes model (15). Residues that maintain longitudinal contacts (e) are 243-245 (blue) and 322-325 (cyan); 202-204 (yellow) and 286 -289 (green); and 41-45 (red) and 166 -169,375 (magenta). Lateral contacts are shown in f: 110 -112 (magenta) bridges with (195-197 (cyan), while the tip of the hydrophobic loop (266 -269, green) would contribute to the bridge of density with a hydrophobic pocket (166, 169, 171, 173, 285, and 289 shown in yellow, and 40 -45 and 63-64 shown in red) formed by residues on the opposite strand. Because we have not rotated the loop from the body of the actin subunit, some of the red residues appear far from the loop. Fig. 2. Three-dimensional reconstruction of ABD2-F-actin complex generated from a subset of segments (n ϭ 8,357) chosen to eliminate heterogeneity. The volume has been filtered to 12-Å resolution and is shown with docked atomic models of actin and ABD2 (a). Actin subdomains are labeled with red numbers, and CH domains of ABD2 are labeled in black. Docking of actin was performed as described in Fig. 1, and CH3 and CH4 of ABD2 were docked independently. The atomic model of ABD2-F-actin complex is filtered to 12-Å resolution (b, blue mesh) and is superimposed on the actual map (b, transparent gray surface). Residues of actin shown to interact with fimbrin are shown as green spheres (c and d) and numbered in red (d), and residues of ABD2 important for interacting with F-actin are shown as yellow spheres (c and d) and numbered in black (d). The actin binding core of fimbrin in the conformation found in the crystal ( 22) is superimposed on the atomic model of actin filament derived from the ABD2-F-actin complex (d). CH-domains are marked as follows: CH1, magenta; CH2, cyan; CH3, red; CH4, orange. assigned unambiguously by using a crystal structure for the fimbrin core. Because no crystal structure exists for the plastin ABD2, we have used the crystal structure ( 22) of the Arabidopsis thaliana fimbrin core (which contains both ABD1 and ABD2). The justification for this is that there is a 38% sequence identity (66% similarity) within ABD2 between human L-plastin and A. thaliana fimbrin, and there are no insertions or deletions of more than three amino acids. The CH3-domain is located at the smaller radius and produces an extensive contact with SD2 of one actin protomer and the lower portion of SD1 of an adjacent protomer within the same long-pitch helical strand (Fig. 2 a andc). The CH4-domain, which is positioned at a higher radius (Ͼ55 Å), has only a weak contact with SD1 (residues 22-25) of actin (Fig. 2 a andc). Strikingly, the binding of ABD2 that we observe is different from any binding previously observed or proposed for other tandem CH-domain proteins, such as utrophin (6), ␣-actinin (23), and even ABD1 of T-fimbrin (2). The differences in binding cannot be due to potential artifacts associated with negatively stained samples ( 6), because at 20-Å resolution, a reconstruction of negatively stained ABD2decorated F-actin is indistinguishable from that of the cryo-EM reconstruction (SI Fig. 5).

Comparison of the reconstruction and the atomic model (containing actin, CH3, and CH4) filtered to 12 Å shows that the actin part of the map and the CH3 region have an excellent agreement with the atomic model (Fig. 2b). The docking of CH4 is unambiguous at 16-Å resolution and provides an excellent match to the reconstruction at that resolution (data not shown), but the CH4 region of the reconstruction does not extend to 12-Å resolution. Such a steep drop in resolution at higher radius suggests that CH4 is partially disordered. Resolution measurements show that the overall map has a Fourier shell correlation (FSC) of 0.5 at 16.7 Å, whereas radial truncation (removing CH4) improves the resolution to 13.3 Å (SI Fig. 4d). Care was taken in such radial truncation to use Gaussian masks of different sizes for the volumes being compared to prevent the mask function from introducing a spurious correlation. Again, this estimation is overly pessimistic because we have a nearly perfect match between the atomic model and the actual reconstruction at 12-Å resolution when CH4 is excluded. To improve the fit of CH4, we had to move the most distal region of CH4 by 14 Å away from its position in the crystal structure (Fig. 3b). Such a movement is consistent with the fact that there is a 3-Å difference in the position of CH4 between two copies of the fimbrin core (when measured at the same distal loop) within the crystal unit cell (22) (SI Movie 1), suggesting flexibility in the interface between the CH3-and CH4-domains.

The position of ABD2 on F-actin in our atomic model is supported by mutagenesis data. All actin residues (K50, D51, K61, E99, and E100) shown to interact with fimbrin (24) are at the interface with ABD2 of fimbrin (Fig. 2 c andd). Interestingly, it was shown that these residues are involved in interaction with both ABDs of fimbrin. Residues R395, K461, F539, and K589 within ABD2 of Arabidopsis fimbrin [using the alignment of Klein et al. (22)] are expected to affect the binding of fimbrin to F-actin, based on mutations in the corresponding residues within yeast fimbrin (A414, D484, F560, and K610, respectively) (25). In our reconstruction, K461 interacts with the upper portion of SD2 of actin (Fig. 2c, red arrows), whereas F539 forms a bridge of density with actin residues 22-25 (Fig. 2c, green arrows). Mutation of R395 may introduce structural alterations in the actin binding site of ABD2 because of its proximity to K461 (Fig. 2d). K589, on the other hand, is located at the most distal tip of CH4 and cannot be involved in any direct interaction with actin.

We can take the entire fimbrin core crystal structure (containing CH1, CH2, CH3, and CH4) and dock it to F-actin based on the binding of CH3 and CH4 that we have established. It can be seen when this is done that K589 (Fig. 2d, black asterisk) is buried at the interface between CH1 (Fig. 2d, magenta ribbons) and CH4 (Fig. 2d, orange ribbons) of fimbrin. Because our atomic model of the ABD2-F-actin complex shows that K589 is not involved in the interaction with F-actin, the most likely explanation for the yeast K610 (A. thaliana K589) mutagenesis result is the proposal that rearrangements of the two ABDs of fimbrin are important for bundling (22). Thus, A. thaliana K589 may govern a conformational change within ABD1 (CH1 and CH2) to make it active in the binding to a second actin filament. When a second actin filament is placed 120 Å away from the filament to which ABD2 is bound (5), CH1 of ABD1 is in close proximity to the binding site on actin previously described (2, 11) for ABD1.

Another important conclusion derived from our reconstruction is that the ATP-binding cleft of actin is more closed than in the control undecorated actin filament (Fig. 3a). In fact, the cleft in actin is more closed than in all existing crystals because we have needed to shift subdomain 2 inwards by 3.5 Å and rotate subdomain 1 by Ϸ12°with respect to their positions in G-actin (20). The opening of the cleft has been shown to destabilize F-actin (26), and the potential stabilization of F-actin by a closure of the cleft is in excellent agreement with biochemical data that either full-sized fimbrin or ABD2 alone can stabilize actin filaments (7,27). An additional means of stabilization of F-actin may arise from the fact that ABD2 is bound to two adjacent protomers along the same long-pitch helical strand in F-actin, and this stapling of adjacent protomers may have an important effect on filament stability. Because it is expected that bundling of actin filaments by fimbrin proceeds simultaneously with polymerization of these filaments (5), the stabilization of nascent F-actin filaments by fimbrin may be an important element in the coordination of polymerization with bundling.

Actin-ABD1 Complexes. The docking of the fimbrin core crystal structure to an ABD2-decorated F-actin filament (Fig. 2d) provides a starting point for understanding cross-linking of adjacent actin filaments by fimbrin. The obvious question is whether ABD1 (containing CH1 and CH2) can bind to a second filament that is 120 Å away from the filament to which ABD2 is bound while in the same conformation seen in the crystal structure of the fimbrin core (containing both ABD1 and ABD2). We have therefore attempted to decorate isolated F-actin filaments with ABD1 alone to perform a similar analysis to that used for the ABD2-decorated filaments. Using the estimated dissociation constant of 0.34 M for the binding of ABD1 to F-actin (7), we incubated 1 M F-actin with 2-4 M ABD1 expecting to see saturated binding. Image analysis and IHRSR reconstruction from negatively stained specimens showed essentially naked F-actin filaments. Using 1 M F-actin with 10-15 M ABD1, we were able to obtain substantial Fig. 3. Perturbations of atomic models were needed to match the reconstruction. The ATP binding cleft of actin in the ABD2-F-actin complex is more closed (a, blue ribbon) than that in the pure F-actin reconstruction (a, green ribbon). This is due to an apparent rotation of subdomain 1 by Ϸ12°and a shift of subdomain 2 by Ϸ3.5 Å. To better fit CH4 into the reconstruction (b, green ribbon), it was rotated with respect to CH3 so that the most distal loop was shifted by 14 Å from its position in the crystal (b, red ribbon).

decoration of F-actin filaments by ABD1 (SI Fig. 6a), but the overall reconstruction generated (SI Fig. 6c) was uninterpretable in terms of what was actin and what was ABD1. This suggested to us that this overall reconstruction was largely artifactual because of the misalignment of both actin and ABD1 in the process of averaging together segments that are structurally diverse and inhomogeneous. Because we have previously shown that polymorphic binding to F-actin can be detected and different modes can be separated (6,8,(28)(29)(30)(31), considerable effort was invested in attempting to separate these segments into homogeneous classes. All such efforts failed.

The simplest explanation is that unlike ABD2, where the tandem CH-domains bind to F-actin in a compact conformation similar to that seen in the fimbrin core crystal structure, the tandem CHdomains in ABD1 can separate, resulting in a multiplicity of different conformations when bound to F-actin. This is consistent with what has been seen in the fimbrin core crystal structures, where two copies of the core (unrelated by crystal symmetry) are present in each asymmetric unit. Although there is a relatively fixed interaction between CH3 and CH4 when comparing these two molecules within the asymmetric unit (SI Movie 1), there is no conservation of the CH1-CH2 interface. The inability to separate out distinct modes of binding for these CH-domains, when such modes could be separated for the tandem CH-domains present in utrophin (6,30), suggests that there is little cooperativity in the modes of fimbrin ABD1 binding to F-actin within any given segment, whereas substantial cooperativity must exist in the case of utrophin.

Discussion

There has been an extensive debate in the literature about whether tandem CH-domains bind to F-actin in an ''open'' or ''closed'' conformation, and whether the interaction of all CHdomains with F-actin is conserved (2,3,5,6,8,30,(32)(33)(34). The structural conservation that has been seen among CH-domains led to the reasonable suggestion that there would be a conserved functional interaction between CH-domains and actin. However, we have shown that the CH-domain within calponin is never actually in contact with actin when calponin is bound to F-actin (8), suggesting that there may have been a divergence between structure and function in the evolution of proteins containing CH-domains. We have also examined the tandem CH-domains in utrophin and shown that the binding to F-actin is polymorphic because the two CH-domains do not maintain a single fixed interaction with each other when attached to F-actin (6,30). We now show that in contrast to the polymorphism in the utrophin tandem CH-domains, the tandem CH-domains in fimbrin ABD2 bind F-actin in a rather fixed manner.

The stoichiometric decoration of F-actin by ABD2 is reminiscent of the decoration of F-actin by myosin S1, but we have been able to achieve a higher resolution in reconstructing this complex than has previously been achieved for any acto-S1 reconstruction (35)(36)(37). An interesting question that we cannot answer at this point is whether the higher resolution is due to the fact that the actin-ABD2 complex is more ordered than acto-S1, with less variability in twist and polymorphism within F-actin, or whether the improvement comes from the image processing scheme that we use (17). The reduction in variability of twist when ABD2 is bound, and the closure of actin's nucleotide binding pocket, may be coupled. Bacterial ParM is a structural homolog of actin (38) that has a very similar fold with two major domains surrounding a nucleotide binding pocket. We have suggested that the much larger variability in twist present in ParM filaments than exists in F-actin is due to the much greater opening of the nucleotide binding pocket in ParM than occurs in F-actin (39).

In contrast to the fixed and stoichiometric binding of ABD2 to F-actin, the binding of ABD1 alone is polymorphic and partial. In fact, we have found that the binding is much more polymorphic than the binding of the utrophin tandem CH-domains to F-actin (6), and we have been unable to reconstruct any ABD1-actin complexes. The partial decoration of F-actin by ABD1 that we have seen is very similar to the partial occupancy that has been reported previously (2,11). However, in those previous reports it was assumed that ABD1 bound in a single mode, albeit at low occupancy, and so a pseudo-atomic model of ABD1 bound to F-actin was constructed from those data (2). Previous evidence for the polymorphic nature of the ABD1 binding comes from the fact that when two different methods were used to construct a difference map between the ABD1-actin complex and pure F-actin, two different results were obtained (2,40). The partial and disordered binding of ABD1 to F-actin, in contrast to the stoichiometric and ordered binding of ABD2, is consistent with the fact that ABD2 significantly protects actin filaments from depolymerization whereas ABD1 provides very little protection (7).

What do our present results tell us about fimbrin's role in bundling actin filaments? The inability to define the interaction between ABD1 and actin means that some speculation is required, but the observations presented here are suggestive. We propose that ABD2 is bound first to one F-actin filament, which induces the closure of the actin cleft that we observe. As with many structural perturbations within F-actin, we expect that there is a cooperativity that results in the stabilization of a region in the nascent actin filament by the transmission of this conformational change to adjacent subunits within the same filament (41,42). In addition, the binding of ABD2 to actin ''activates'' ABD1 so that it may bind in a more ordered manner than that observed for free ABD1 to another actin filament with high affinity. The fact that mutagenesis of the residue (K610 in yeast) equivalent to K589 in Arabidopsis fimbrin ABD2 (Fig. 2d) can suppress a temperature-sensitive mutation in yeast actin is quite consistent with our picture that the binding of ABD2 to one F-actin filament may be needed to activate ABD1 to bind to an adjacent filament. The shift of CH4 that we observe from the fimbrin core crystal structure when ABD2 is bound to F-actin might be part of the mechanism for the activation of ABD1. Alternatively, mutation of K610 in yeast fimbrin (K589 in A. thaliana fimbrin) may change the tightly packed interface seen between CH4 and CH1 in the fimbrin core structure and thus activate ABD1 (CH1 and CH2) in the absence of ABD2 binding to F-actin. Thus, the yeast K610R mutation may increase the overall affinity between actin and fimbrin (25), which will rescue a defect in actin.

As databases of gene sequences grow exponentially, more tools are needed for annotation to provide biological meaning. Many, if not most, proteins have been found to have a modular structure, and the similarity of modules is being used to assign similar functions to common modules in different proteins. We show here that the structural similarity among CH1, CH2, CH3, and CH4 in the fimbrin core does not necessarily dictate similar properties or functions. In fact, the presence of CH-domains in proteins only directly tells us about the evolutionary origins of this module and not about the function of this module in any protein of interest. Further detailed studies of fimbrin, including a high-resolution structure of the ABD1-F-actin complex, are still required to build an atomic model of actin-fimbrin bundles.

Methods

Sample Preparation and Microscopy. Actin (2.5 M) was polymerized in 20 mM Mops buffer (pH 7.2), 50 mM KCl, 1 mM MgCl2, 0.5 mM EGTA, 0.5 mM DTT, and 0.2 mM ATP for 2.5 h before grids were prepared. Human L-plastin fragments ABD1 and ABD2 were prepared as described in ref. 7. ABD2 was used at 2-4 M concentrations when incubated with F-actin at 1 M concentration. All cryo-EM was done on a Tecnai F20 FEG microscope operated at 200 keV at a magnification of ϫ50,000, and negatively stained samples were imaged on a Tecnai T12 microscope operated at 120 keV at a magnification of ϫ30,000.

Image Processing. The SPIDER software package (43) was used for most image processing, but the EMAN package (44) was used to determine the defocus values in the micrographs and to extract filament images from micrographs. Pure F-actin. A Nikon COOLPIX 8000 scanner was used to digitize 74 cryo-EM micrographs having a defocus range from Ϫ1.5 to Ϫ3.8 m at a raster of 2.38 Å per pixel. Initial correction for the contrast transfer function (CTF) was made by multiplying each image by its theoretical CTF. From these CTF-corrected images, 28,134 short (200 pixels long) overlapping segments were extracted. Three model volumes were created by using crystal structures of G-actin (20) having actin protomers in the ''canonical'' state, with missing SD2, and finally in the ''tilted'' state (14). These volumes were scaled to 4.76 Å per pixel and projected into 100 ϫ 100-pixel images with an azimuthal rotational increment of 4°, generating 270 reference projections (3 ϫ 90). The F-actin segments were down-sampled to 4.76 Å per pixel and cross-correlated with the 270 reference projections. To check the quality of the sorting, the model volumes were azimuthally rotated by 2°and a second set of reference images was created and used for a new cross-correlation sorting of the image segments. Only 25,567 F-actin segments were assigned to the same class in both crosscorrelations, and these were used for the final reconstruction. A set of 10,986 segments (sampled at 2.38 Å per pixel), selected as similar to the ''canonical'' state of F-actin, was reconstructed with the IHRSR method ( 17) and after 30 iterations yielded a stable solution of 166.6°/27.6 Å. The volume was corrected for the CTF (because images had been effectively multiplied by the CTF twice, once by the microscope and once by us) by using a Wiener filter assuming that the signal-to-noise ratio in the volume was very large, and a range of negative B-factors was used to amplify high frequencies in the reconstruction that were damped by the envelope function of the microscope. The most reasonable volume was used to generate an atomic model. The spherically averaged power spectra of the actual reconstruction and the atomic model were then compared and used to adjust structure factor amplitudes in the reconstruction in a resolution-dependent manner, and this new volume was used for the final modeling. UCSF Chimera software (45) was used to fit crystal structures into the experimental maps. Atomic coordinates from crystal structures were converted to density maps, and these were filtered to the resolution of the experimental map and docked both manually and by using the Chimera automated procedure. Both approaches gave the same result.

The conservative FSC ϭ 0.5 criterion was used for resolution determination. A widely used approach has been to split an aligned data set into two halves yielding two volumes for FSC comparison, but this method can yield an overly optimistic resolution value due to alignment of noise (46,47). We have modified the conventional approach by dividing the images into two sets and then using the IHRSR procedure on these two sets starting each from a different helical symmetry. The two structures converge to a common symmetry (SI Fig. 4a), and the resultant volumes do not have noise aligned to a common reference. However, the smaller number of images present in each half data set suggests that the resolution of each half set will be less than the resolution of the combined reconstruction under conditions where the resolution is limited by the number of particles. Thus, the 12.5-Å resolution that we measure by this method in our undecorated F-actin map (SI Fig. 4b) is the most pessimistic resolution estimation. ABD2-F-actin complex. A set of 65 micrographs (defocus range of Ϫ1.3 to Ϫ4.5 m) was digitized as described for pure F-actin, corrected for CTF, and used to collect 22,210 short segments (200 pixels long). The overall reconstruction suggested that all filaments were fully occupied because the full density of ABD2 was visible without any prior sorting. However, the resolution of the overall reconstruction was Ϸ18 Å. To improve the resolution, three model volumes having actin protomers in different structural states were created, but ABD2 was attached to each as observed in the overall reconstruction. In the first model, the ATP-binding cleft was closed; in the second model, it was wide open; and in the third model, actin protomers were in the ''tilted'' state. The model volumes were used to create a reference set of images as described earlier. The majority of segments yielded the best correlation with the model having the ATP binding cleft closed (n ϭ 9,051), and images that had reasonably small in-plane rotation angles (Ͻ10°) were used for the reconstruction (n ϭ 8,357). These segments were then reconstructed by using a featureless solid cylinder as an initial starting model. After 60 iterations of the IHRSR procedure, the set yielded a stable solution of 166.5°/27.8 Å. The same solid cylinder was used as an initial reference for reconstructing the other sets. The reconstruction of segments that possessed the best correlation with the model having the open ATP binding cleft showed that CH4 of fimbrin ABD2 was less ordered, and the occupancy was somewhat lower than that in the first set. The third set yielded a reconstruction suggesting that mostly noisy and disordered filaments were assigned to that class. Correction for the CTF in the final volume and model building was done similarly to the naked F-actin map. The coordinates for the ABD2-actin model have been deposited in the Protein Data Bank (PDB ID code 3BYH). Negatively stained ABD2-F-actin complex. We collected 8,960 segments of F-actin decorated with ABD2 from negatively stained samples, each 100 pixels long and sampled at 4.16 Å per pixel. This set was reconstructed by using the IHRSR approach and after 60 iterations yielded a symmetry of 166°/27.7 Å. Negatively stained ABD1-F-actin complex. A set of 4,210 segments (100 pixels long, 4.16 Å per pixel) was used in the IHRSR procedure and converged to a symmetry of 165.3°/29.5 Å. Not only was this symmetry unexpected (given the fixed axial rise in F-actin of Ϸ27.3 Å), but the reconstruction was uninterpretable in terms of what was actin and what was ABD1. Attempts to use reconstructions of F-actin decorated with utrophin (6), ␣-actinin (unpublished data), and ABD2 of fimbrin to sort this set into more homogeneous classes did not succeed.

Fig. 1 .

 1 Fig. 1. Cryo-EM of the pure F-actin control. A typical segment used for image processing (480 Å long) is shown within the red box in the cryo-EM micrograph of pure F-actin (a). Actin filaments decorated with ABD2 of fimbrin (b) are noticeably thicker than pure actin filaments. (Scale bar: 500 Å.) Three-dimensional reconstruction of F-actin in the ''canonical'' state (c) was generated with the IHRSR method (17), using a subset (n ϭ 10,986) of the total segments collected after sorting to exclude structural variability, such as tilted actin and segments where subdomain 2 was disordered. Actin subdomains are labeled with red numbers. To improve the fitting, the actin monomer was divided into three parts: SD1 (residues 2-33, 70 -145, and 336 -375), SD2 (34 -69), and SD34 (146 -335). These parts were fit as rigid bodies, and the corresponding symmetry was imposed to build a model filament (c, blue ribbons). To evaluate the similarity between the model and the actual reconstruction, the atomic model was filtered to 12 Å (d, transparent surface) so that it may be compared with the original volume (c, transparent surface). Our model is in agreement with the contacts between the protomers in the Holmes model(15). Residues that maintain longitudinal contacts (e) are 243-245 (blue) and 322-325 (cyan); 202-204 (yellow) and 286 -289 (green); and 41-45 (red) and 166 -169,375 (magenta). Lateral contacts are shown in f: 110 -112 (magenta) bridges with(195-197 (cyan), while the tip of the hydrophobic loop (266 -269, green) would contribute to the bridge of density with a hydrophobic pocket (166, 169, 171, 173, 285, and 289 shown in yellow, and 40 -45 and 63-64 shown in red) formed by residues on the opposite strand. Because we have not rotated the loop from the body of the actin subunit, some of the red residues appear far from the loop.

͉ www.pnas.org͞cgi͞doi͞10.1073͞pnas.0708667105 Galkin et al.

͉ www.pnas.org͞cgi͞doi͞10.1073͞pnas.0708667105 Galkin et al.

ACKNOWLEDGMENTS. This work was supported by National Institutes of

Health Grant GM081303 (to E.H.E.).

ID code 3BYH).