The application of information technology in the field of biomedicine has become increasingly important over the last several years. This paper presents an intelligent dynamic architecture for knowledge data discovery in biomedical databases. The core of the system is a type of agent that integrates a novel strategy based on a case-based planning mechanism for automatic reorganization. This agent proposes a new reasoning agent model, where the complex processes are modeled as external services. The agents act as coordinators of Web services that implement the four stages of the case-based planning cycle. The multi-agent system has been implemented in a real scenario to classify leukemia patients. The classification strategy includes services to analyze patient's data, and the results obtained are presented within this paper.
The continuous growth of techniques for obtaining cancerous samples, specifically
those using microarray technologies, provides a great amount of data. Microarray has
become an essential tool in genomic research, making it possible to investigate global
genes in all aspects of human disease [
This paper presents an innovative solution to model decision support systems in
biomedical environments, based on a multi-agent architecture which allows
integration with Web services and incorporates a novel planning mechanism that
makes it possible to determine workflows based on exising plans and previous results.
The Multiagent System centers on obtaining a self-adaptive biomedical organizational
model, making it possible to represent laboratory workers within a virtual
environment and the interactions that take place, in order to carry out daily
classification tasks. The core of system is a CBP-BDI (Case-based planning) (Belief
Desire Intention) agent [
The next section describes the main characteristics of the proposed multiagent system and briefly explains its components. Section 3 presents a case study consisting of a distributed multi-agent system for cancer detection scenarios. Finally section 4 presents the results and conclusions obtained. 2.
Nowadays, having software solutions at one's disposal that enforce autonomy,
robustness, flexibility and adaptability of the system to develop is completely
necessary. The dynamic agents organizations that auto-adjust themselves to obtain
advantages from their environment seems a more than suitable technology to cope
with the development of this type of systems. The integration of multi-agent systems
with SOA (Service Oriented Architecture) and Web Services approaches has been
recently explored [
The approach presented in this paper is an organizational model for biomedical
environments based on a multi-agent dynamic architecture that incorporates agents
with skills to generate plans for analysis of large amounts of data. The core of the
system is a novel mechanism for the implementation of the stages of CBP-BDI
mechanisms through Web services that provides a dynamic self-adaptive behaviour to
reorganize the environment. Moreover, the system provides communication
mechanisms that facilitate integration with SOA architectures. The multiagent system
was initially designed to model the laboratory environments oriented to the processing
of data from expression arrays. To do this, the system defined specific agent types and
services. The agents act as coordinators and managers of services, while the services
are responsible for carrying out the processing of information by providing replication
features and modularity. Agents are available to run on different types of devices, so
different versions were created to suit each one. The types of agents are distributed in
layers within the system according to their functionalities, thus providing an
organizational structure that includes an analysis of the information and management
of the organization, and making it possible to easily add and eliminate agents from the
system. The agent layers constitute the core and define a virtual organization for
massive data analysis, as can be seen in Figure 1. Figure 1 shows four types of agent
layers:
• Organization: The agents will be responsible for conducting the analysis of
information following the CBP-BDI [
On the other hand, the services layer is divided into two groups: • Analysis Services: The analysis services are services used by analysis agents for carrying out different tasks. The analysis services include services for preprocessing, filtering, clustering and extraction of knowledge. Figure 1 illustrates how these services are invoked by the analysis layer agents in order to carry out the different tasks corresponding to microarray analysis. • Representation Services: They generate graphics and result tables.
Within the services layer, there is a service called Facilitator Directory that provides information on the various services available and manages the XML file for the UDDI (Universal Description Discovery and Integration). To facilitate communication between agents and services the architecture integrates a communication layer that provides support for the FIPA-ACL and SOAP protocols.
Figure 1 shows the connections between the diagnosis agent (in the organization layer) with the agents in the analysis layer and the services. The connections represent a plan. A diagnosis incorporates a filtering process, carried out by an analysis agent that selects the sequence of services for the plan. Then, a clustering agent selects the optimum service. Finally, the knowledge extraction obtains the relevant probes.
Nowadays, there exist different possibilities to services planning and composition.
One of the most important is services composition using HTN (Hierarchical Task
Network) and HTN planners as SHOP2 [
The coordinator agent is the core of the system, since provides the ability for
selforganization. The agents in the organization layer have the capacity to learn from the
analysis carried out in previous procedures. They adopt the model of reasoning CBP,
a specialization of case-based reasoning (CBR) [
The CBP-BDI agents stem from the BDI model [
The CBP-BDI agent type presented in this paper acts as coordinator of services. The terminology used is the following: The environment M and the changes that are produced within it, are represented from the point of view of the agent. Therefore, the world can be defined as a set of variables that influence a problem faced by the agent
The beliefs are vectors of some (or all) of the attributes of the world taking a set of concrete values
M = {τ 1,τ 2 ,L,τ s } with s < ∞
B = {bi / bi = {τ 1i ,τ 2i ,L,τ ni }, n ≤ s ∀i ∈ N}i∈N ⊆ M
A state of the world ej є E is represented for the agent by a set of beliefs that are true at a specific moment in time t. i represents a belief of the N.
Let E={ej}jєN set of status of the World if we fix the value of t then
etj = {b1jt , b2jt ,Lbrjt }r∈N ⊆ B ∀j,t
The desires are imposed at the beginning and are applications between a state of the current world and another that it is trying to reach
Intentions are the way that the agent’s knowledge is used in order to reach its objectives. A desire is attainable if the application i, defined through n beliefs exists:
In our model, intentions guarantee that there is enough knowledge in the beliefs base for a desire to be reached via a plan of action. We define an agent action as the mechanism that provokes changes in the world making it change the state,
Agent plan is the name we give to a sequence of actions that, from a current state e0, defines the path of states through which the agent passes in order to reach the other world state.
a j : Ee i → E → aj (ei )=ej pn : Ee0 → E → pn(e0)=en d : E e0 → E → e* n) i : BxBxL xBxE (b1, b2,LLLL, bn , e0 )
→→ Ee* pn (e0 ) = en = an (en−1) = L = (an oLo a1)(e0 ) pn ≡ an o L o a1
Based on this representation, the CBP-BDI coordinator agents combine the initial state of a case, the final state of a case with the goals of the agent, and the intentions with the actions that can be carried out in order to create plans that make it possible to reach the final state. The actions that need to be carried out are services, making a plan an ordered sequence of services. It is necessary to facilitate the inclusion of new services and the discovery of new plans based on existing plans. Services correspond to the actions that can be carried out and that determine the changes in the initial problem data. Each of the services is represented as a node in a graph. The presence of an arch that connects to a specific node implies the execution of a service associated with the end node. Figure 2 provides a graphical representation of a service plans. As shown, the first graph has only one path and contains nodes that are not (1) (2) (3) (4) (5) (6) (7) connected. The path defines the sequence of services from the start node until the end node. The plan described by the graph is defined by the sequence (S7 о S5 о S3 о S1)( e0). e0 represents the original state that corresponds to Init, which represents the initial problem description e0. Final represents the final state of the problem e*.
CBP-BDI agents use the information contained in the cases in order to perform
different types of analyses. As previously explained, an analysis assumes the
construction of the graph that will determine the sequence of services to be
performed. The construction process for the graph can be broken down into a series of
steps that are explained in detail in the following sub-sections:
1. Generate the directed graph with the information from the different plans.
2. Generate a TAN (Tree Augmented Naive Bayes) classifier for the cases with the
best and worst output respectively, using the Friedman-Godsmidtz [
The different plans are represented in the graphs. The plans represented in graphical form are joined to generate one directed graph that defines the new plans based on the minimization of a specific metric. For example, given the graphs shown in figure 2, a new graph is generated that joins the information corresponding to both graphs.
The dual connection of the nodes is indicated only to represent the existence of a
connection between the two graphs, although it is not actually necessary to represent
more than one connection per arc. Each of the arcs in the graph for the plans has a
corresponding weight according to which it is possible to calculate the new route to
be executed. This value is estimated based on the efficiency of the plans recovered as
indicated in section 2.1.4. When constructing the graph of plans, the weights are
estimated based on the existing plans by applying a bayesian network. The entry data
to the bayesian network is broken down into the following elements: Plans with a
high efficiency are assigned to class 1 and plans with a low efficiency are assigned to
class 0. The Bayesian network is calculated for each of the classes according to the
recovered plans, following the Friedman-Goldsmidtz [
The TAN classifier is constructed based on the plans recovered that are most similar
to the current plan, distinguishing between efficient and inefficient plans to generate
the model. Thus, by applying the Friedman-Goldsmidtz [
x∈X y∈Y z∈Z Based on the previous metric, the maximal tree is constructed. (8)
Once the TAN model has been calculated for each of the classes, we proceed to calculate the probability of execution for each of the services. These probabilities influence the final value of the weights assigned to the arcs in the graph. The probabilities are calculated according to the TAN model. Assuming that the set of random variables can be defined as U = {X1, X2,…, Xn}, we can assume that the variables are independent. The probabilities are represented by P( xi | π xi ) where xi is a value of the variables Xi and π xi ∈ Π X i whereπ xi represents one of the parents for the node Xi. Thus, a Bayesian network B, defines a single set probability distribution over U given for
P( X 1, X 2 ,..., X n ) = P( X n | X n−1,..., X1 ) ⋅ P( X n−1,..., X1 ) = n n ∏i=1 P( X n | X n−1,..., X 1 ) = ∏i=1 P( X i | Π Xi )
Using the TAN model, we can define the probability that a particular number of services may have been executed for classes 1 and 0. This probability is used to determine the final value for the weight with regards to the quality of the plans recovered. Assuming that the probability of having executed service i for class c is defined as follows P(i,c) the weight of the arcs is defined according to the following formula. The function has been defined in such a way that the plans of high quality are those with values closest to zero.
cij = P( j,1) ⋅ I (i, j,1) ⋅ ti1j − P( j,0) ⋅ I (i, j,0) ⋅ ti0j
∑ (1 − (q( p) − min(q(s)))) + 0.1 ti1j = p∈Gi1j ,s∈G1
∑ q( p) − min(q(s)) + 0.1 ti0j = p∈Gi0j ,s∈G0 #Gi1j #Gi0j (9) (10) (11) where: • I(i,j,c) is the probability that service i for class c is executed before of service j • P(j,c) is the probability that service j for class c is executed. The value is obtained based on the Bayesian network defined in the previous step. • Gsij is the set of plans that contain an arc originating in j and ending in i for class s. • Gs is the set of plans for class s. • q(p) is the quality of plan p that also defined the execution time for the plan. The significance depends on the measure of optimization in the initial plan. • #Gsij the number of elements in the set. • cij is the weight for the connection between the start node j and the end node i.
Once the graph for the plans has been constructed, the minimal route that goes from the start node to the end node is calculated. In order to calculate the shortest/longest route, the Dijkstra algorithm is applied since there are implementations for the order n*log n. To apply this algorithm, it is necessary to add to each of the edges the absolute value of the edge with a higher negative absolute value, in order to remove from the graph those edges with negative values. The route defines the new plan to execute and depends on the measure to maximize or minimize.
The multiagent architecture presented in this paper has been used to develop a
decision support system for the classification of leukemia and brain tumors patients,
and three case studies were established. The first case study uses data from patients
suffering from leukemia and focuses on the classification of the type of leukemia. The
second case study also analyzes the data from leukemia patients, but in this case
focuses on the type of CLL leukemia and attempts to classify the patients in the three
existing subtypes. Finally, the goal of the third case study is to classify patients based
on the type of brain tumor. The data for leukemia patients was obtained with a HG
U133 plus 2.0 chip and corresponded to 212 patients affected by 5 different types of
leukemia (ALL, AML, CLL, CML, MDS) [
The services implement the algorithms that allows the analysis expression of the
microarrays [
Preprocessing Service: This service implements the RMA (Robust Multi-array
Average) [
Filtering Services: Eliminate the variables that do not allow classification of
patients by reducing the dimensionality of the data. Three services are used for
filtering: (i) Variables with low variability have similar values for each of the
individuals, so they are not significant for the classification process. (ii) All remaining
variables that follow a uniform distribution are eliminated. The contrast of
assumptions followed uses the Kolmogorov-Smirnov [
Clustering Service: It addresses both the clustering and the association of a new
individual to the group more appropriate. The service used is the ESOINN (Enhanced
self-organizing incremental neuronal network) [
Knowledge Extraction Service: The extraction of knowledge technique applied has
been CART (Classification and Regression Tree) [
The agents in the analysis layer implement the CBP reasoning model and, for this, select the flow for services delivery and decide the value of different parameters based on previous plans made. A measure of efficiency is defined for each of the agents to determine the best course for each phase of the analysis process. In the analysis layer, at the stage Preprocessed only a service is available. The efficiency is calculated by the deviation in the microarray. At the stage of filtering, the efficiency of the plan p is calculated by the relationship between the proportion of probes and the resulting proportion of individuals falling ill.
e( p) = s + i' (12)
N I
Where s is the final number of variables, N is the initial number of probes, i’ the number of misclassified individuals and I the total number of individuals. In the phase of clustering and classification the efficiency is determined by the number of misclassified individuals. Finally, in the process of extracting knowledge at the moment, efficiency is determined by the number of misclassified individuals.
In the organization layer, the diagnosis agent chooses the agents for the expression
analysis [
This paper has presented the a self-adaptive multiagent architecture and its application to three real problems. The characteristics of this novel architecture facilitate a organizational-oriented approach where the dynamics of a real scenario can be captured and modelled into CBP-BDI agents. The tests were oriented both to evaluate the efficiency and the adaptability of the approach. The first experiment consisted of evaluating the services distribution system in the filtering agent for the case study that classified patients affected by different types of leukemia. According to the identification of the problem described in table 1, the filtering agent selected the plans with the greatest efficiency, considering the different execution workflows for the services that are in the plans. Table 1 shows the efficiency obtained for the service workflows that provided the best results in previous experiences. The values in the
Once the service distribution process and the selection of parameters for a specific case study have been evaluated, it would appear convenient to evaluate the adaption of this mechanism to case studies of a different nature. To do so, we once again recover the plans with the greatest efficiency for the different workflows and case studies, and proceed to calculate the Bayesian network and the set of probabilities associated with the execution of services as mentioned in sections 2.1.2 and 2.1.3. Once the graph plans have been generated, a more efficient plan is generated according to the procedures indicated in section 2.1.5, with which we can obtain the plan that best adjusts to the data analysis. Table 2 shows the plans generated by the filtering process that best adjusts to the different case studies.
In Figure 3 it is possible to observe the performance of the agents at the organization and analysis layers. 11 plans were conducted based on manual planning and the results were compared with the automatic analysis provided by the multiagent system. In the manual planning a human expert configures the service's parameters, such as if the RMA will use interquantile normalization, or the sequence to execute the services. Each of the agents of the organization layer selects the agents from the analysis layer and, each of these agents in turn selects the services and configuration parameters. The different kinds of agent from the analysis layer can be seen at the bottom of Figure 3 (the name of the agents from the organization layer is indicated in the right of the graphics). In each chart the efficiency measure used is shown. The surface for the CBP-BDI agent is the highest efficiency according to th e definitions. 8 6 ccynE ie4 if2 0 100 80 cy60 iecn40 i fE20 0
Laboratory
manual CBP-BDI Doctor
CBP-BDI 1 2 3 4 p5lans6 7 8 9 10 11
manual 1 2 3 4 5plan6s 7 8 9 10 11 d e s s e c o r p e r P leedg itcon onKw trxaE 0,4 yc0,3 ien0,2 c i fE0,1 0 80 y60 icn40 e ifcE20 0
Diagnosis
manual
CBP-BDI 1 2 3 4 5plan6s 7 8 9 10 11
manual
CBP-BDI 1 2 3 4 p5lan6s 7 8 9 10 11 d e litr e F n o it a c if s s a l C
With regards to the classification process, we were able to obtain promising results for each of the case studies. As shown in figures 4a 4b 4c, the probes recovered by the knowledge extraction agent are those that provide the relevant information that makes it possible to classify new individuals. In the first image, we can see the 3 probes that best characterize the patients with CLL leukemia. In the second image, we can see the 3 subtypes of leukemia. Finally, the last image represents the patients with anaplastic and oligodendroglioma tumors. The multi agent system simulates the behavior of experts working in a laboratory, making it possible to carry out a data analysis in a distributed manner, as normally done by experts. The system distributes the functionality among Web services, automatically calculates the expression analysis and allows the classification of patients from the microarray data. Our approach improves the performance provided by the manual procedure for selecting workflow analyses.