Edited by S. Istrail, P. Pevzner, and M. Waterman

Editorial Board: A. Apostolico S. Brunak M. Gelfand T. Lengauer S. Miyano G. Myers M.-F. Sagot D. Sankoff R. Shamir T. Speed M. Vingron W. Wong

Subseries of Lecture Notes in Computer Science

Corrado Priami (Ed.)

Transactions on Computational Systems Biology VIII


Series Editors

Sorin Istrail, Brown University, Providence, RI, USA

Pavel Pevzner, University of California, San Diego, CA, USA

Michael Waterman, University of Southern California, Los Angeles, CA, USA

Editor-in-Chief Corrado Priami

The Microsoft Research - University of Trento Centre for Computational and Systems Biology Piazza Manci, 17, 38050 Povo (TN), Italy E-mail: [email protected]

Library of Congress Control Number: 2007938331

CR Subject Classification (1998): J.3, F.1, F.4, I.6 LNCS Sublibrary: SL 8 - Bioinformatics ISSN 1861-2075

ISBN-10 3-540-76638-3 Springer Berlin Heidelberg New York ISBN-13 978-3-540-76638-4 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law.

Springer is a part of Springer Science+Business Media

© Springer-Verlag Berlin Heidelberg 2007 Printed in Germany

Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12187638 06/3180 5 4 3 2 1 0


This issue of the journal reports regular papers. The first contribution is by Falko Dressier and discusses self-organizing mechanisms in computer networks. The second contribution is by Preetam Ghosh, Samik Ghosh, Kalyan Basu and Sa-jal K. Das and deals with a stochastic event based simulation technique to estimate protein-ligand docking time. The third contribution is by Morteza Analoui and Shahram Jamali, and it deals with the interpretation of the Internet as a biological environment to study congestion phenomena. The fourth contribution is by Corrado Priami and it discusses how computational thinking in biology can be implemented through the use of process calculi. The last contribution is by Peter Saffrey, Ofer Margoninski, James Hetherington, Marta Varela-Rey, Sachie Yamaji, Anthony Finkelstein, David Bogle and Anne Warner and it deals with management information systems in biology. Finally we publish a corrected version of a paper by Ruet and Remy published in the previous volume of the journal.

July 2007

Corrado Priami

LNCS Transactions on Computational Systems Biology — Editorial Board

Corrado Priami, Editor-in-chief Charles Auffray

Matthew Bellgard Soren Brunak Luca Cardelli Zhu Chen Vincent Danos Eytan Domany

Walter Fontana Takashi Gojobori Martijn A. Huynen

Marta Kwiatkowska Doron Lancet Pedro Mendes Bud Mishra

Satoru Miayano Denis Noble Yi Pan

Alberto Policriti Magali Roux-Rouquie Vincent Schachter Adelinde Uhrmacher Alfonso Valencia

University of Trento, Italy

Genexpress, CNRS and Pierre and Marie Curie

University, France Murdoch University, Australia Technical University of Denmark, Denmark Microsoft Research Cambridge, UK Shanghai Institute of Hematology, China CNRS, University of Paris VII, France Center for Systems Biology, Weizmann Institute, Israel

Santa Fe Institute, USA

National Institute of Genetics, Japan

Center for Molecular and Biomolecular

Informatics, The Netherlands University of Birmingham, UK Crown Human Genome Center, Israel Virginia Bioinformatics Institute, USA Courant Institute and Cold Spring Harbor Lab, USA

University of Tokyo, Japan University of Oxford, UK Georgia State University, USA University of Udine, Italy CNRS, Pasteur Institute, France Genoscope, France University of Rostock, Germany Centro Nacional de Biotecnologa, Spain

Table of Contents

Bio-inspired Network-Centric Operation and Control for Sensor/Actuator Networks 1

A Computationally Fast and Parametric Model to Estimate Protein-Ligand Docking Time for Stochastic Event Based Simulation ... 14

Equation-Based Congestion Control in the Internet Biologic

Environment 42

Computational Thinking in Biology 63

End-to-End Information Management for Systems Biology 77

On Differentiation and Homeostatic Behaviours of Boolean Dynamical Systems (Corrected Version) 92

Author Index 103

Bio-inspired Network-Centric Operation and Control for Sensor/Actuator Networks

Falko Dressler

Autonomic Networking Group, Dept. of Computer Science 7, University of Erlangen-Nuremberg, Germany [email protected], dressier/

Abstract. Self-organization mechanisms have been investigated and developed to efficiently operate networked embedded systems. Special focus was given to wireless sensor networks (WSN) and sensor/actuator networks (SANET). Looking at the most pressing issues in such networks, the limited resources and the huge amount of interoperating nodes, the proposed solutions primarily intend to solve the scalability problems by reducing the overhead in data communication. Well-known examples are data-centric routing approaches and probabilistic techniques. In this paper, we intend to go one step further. We are about to also move the operation and control for WSN and SANET into the network. Inspired by the operation of complex biological systems such as the cellular information exchange, we propose a network-centric approach. Our method is based on three concepts: data-centric operation, specific reaction on received data, and simple local behavior control using a policy-based state machine. In summary, these mechanisms lead to an emergent system behavior that allows to control the operation of even large-scale sensor/actuator networks.

1 Introduction

In the communications area, there is a strong research focus on networked embedded systems because of their broad diversity in application domains. Especially, wireless sensor networks (WSN) have become popular for many applications. Similarly, there is a growing demand for sensor/actuator networks (SANET).

Sensor networks are composed of numerous small, independently operating sensor nodes [1]. Such sensors nodes are self-contained units consisting of a battery, radio communication, sensors, and some minimal amount of on board computing power. While the application scenarios are manifold [2], the operation of such WSNs is still challenging [3], basically due to the limited resources in terms of CPU power, storage, and, first of all, energy [4]. Within a WSN, nodes are thought to be deployed, to adapt to the environment, and to transmit data among themselves and/or to a given base station. The research topics include efficient communication in terms of resource consumption, reliability, and scalability [2,5]. Because sensor nodes are usually battery operated, many efforts

C. Priami (Ed.): Trans. on Comput. Syst. Biol. VIII, LNBI 4780, pp. 1-13, 2007. © Springer-Verlag Berlin Heidelberg 2007

have been made to develop energy-efficient algorithms and protocols for communication in WSNs [6].

Usually, WSNs are thought to be dynamic in terms of the current availability, i.e. they care about the potential removal and addition of sensor nodes. Dynamics in terms of mobility is concerned in sensor/actuator networks. Basically, SANETs consist of sensor networks that are enhanced by additional actuation facilities [3]. In most application scenarios, mobile robot systems are used as actuation facilities [7]. Nevertheless, we concentrate on general purpose actuation controlled by measures from corresponding sensor nodes. Therefore, the same network infrastructure is used for actuation control as well as for sensor data collection.

There are many application scenarios for WSNs and SANETs. The most popular examples include the service as first responders in emergency situations [8] and the supervision and control of challenging environments such as the monitoring of animals [9].

of such networks is one of the most challenging issues. Typically, a central control loop is employed consisting of the following actions: measurement, transmission to a base station, (external) analysis, transmission to the actuation devices, actuation. Besides the increased network load, severe delays might be introduced. Driven by the limited resources, mechanisms for network self-organization have been proposed for higher scalability. Most of these approaches focus on efficient communication in WSNs, e.g. directed diffusion as a data-centric communication paradigm [10], and on stateless task allocation in SANETs [11]. Similar issues have been addressed in the artificial intelligence domain. Agent-based systems have been developed that enable an efficient distributed control in uncertain environments [12]. Nevertheless, there are still many unsolved issues such as predictability of an action, reliability of the communication, and boundaries for response times.

In this paper, we present and discuss an approach for in WSNs and SANETs that prevents the necessity of the described control loop or reduces the loop to a few neighboring nodes within the network, respectively. Inspired by the information handling in cell biology, we have built a rule-based system that allows to achieve all decisions within the network itself. There is no external control required. Nevertheless, we propose to allow such external intelligence for the handling of unexpected situations. The adaptive rule system has the inherent property of being self-learning by inducing new rules that match previously unknown situations. Therefore, our method provides at least limited control in a system showing an emergent behavior.

The network-centric control system allows to operate even in scenarios with the following challenging properties:

— Mobility of nodes - commonly it is believed that sensor networks being stationary, nowadays, mobility is a mayor concern

— Size of the network - much larger than in a infrastructure networks

— Density of deployment - very high, application domain dependent

— Energy constraints - much more stringent than in fixed or cellular networks, in certain cases the recharging of the energy source is impossible

The main contributions of the paper can be summarized as follows. An approach is presented that features localized data analysis and diffuse communication of measurement and computation results based on the content of the information instead of topology information and central management. We adapted signaling pathways known from cell biology to achieve an emergent behavior of the addressed complex system consisting of sensors and actuators. Using simple rules that are pre-programmed into network nodes, the network becomes able to solve aggregation or decision problems without having a global view to the behavior of the entire system.

The rest of the paper is organized as follows. Section 2 depicts the shifting paradigms to network-centric operation and control in massively distributed sensor/actuator networks. In section 3, the rule-based state machine for localized actuation control is explained. This description is followed by a discussion in section 4 and a conclusion in section 5.

2 Shifting Paradigms: Network-Centric Operation and Control

The objective of this paper is to discuss the potentials of network-centric control and operation in sensor/actuator networks. We developed a scheme based on three principles: data-centric operation, specific reaction on received data, and simple local behavior control using a policy-based state machine. We start with a high-level motivation for the presented approach, followed by a detailed description of the involved algorithms, and a discussion that is meant to be a starting point for further contemplation.

2.1 Need for Network-Centric Control

The coordination and control of sensor/actuator networks is still an emerging research area. Sensor networks have been enhanced by mobile robots. The resulting system is continuously examining the environment using sensors (measurement). The measurement data is transmitted to a (more or less) central system for further processing, e.g. optimizations using global state information. Then, the actuators are controlled by explicit commands that are finally executed (actuation). Basically, this scheme is usually used because the involved components (sensors, actuators) do not have resources that allow to cover the global state. The scheme is depicted in figure 1 (left). The measurement and the control loop are shown by corresponding arrows. Obviously, long transmission distances have to be bridged leading to unnecessarily high transmission delays as well as to a questionable communication overhead in the network, i.e. possible network congestion and energy wastage.

The favored behavior is shown in figure 1 (right). Self-organization methodologies are used to provide a network-centric actuation control, i.e. a processing of measurement data within the network and a direct interaction with associated, i.e. co-located actuators. How can we build a system that behaves in this fashion

Fig. 1. Operation and control of a SANET: centralized (left), network-centric (right)

and that shows the desired emergent behavior? We tried to adapt mechanisms as known from cell biology as described in the next section. The result is a data-centric message forwarding, aggregation, and processing. The key requirements can be summarized as follows:

— Self-organized operation without central control

— Allowance for centralized "helpers" and self-learning properties

— Reduced network utilization

— Accelerated response, i.e. in-time actuation

2.2 An Excursion to Nature - Cellular Signaling Pathways

The turn to nature for solutions to technological questions has brought us many unforeseen great concepts. This encouraging course seems to hold on for many aspects in technology. Many efforts were made in the area of computer technology employing mechanisms known from biological systems [13]. For this work, we concentrate on information transmission and reaction capabilities employed by signaling pathways for inter-cellular communication [14].

The focus of this section is to briefly introduce the information exchange in cellular environments and to extract the issues in computer networks that can be addressed by the utilization of these mechanisms [15,16]. Similar to the structure, the intercommunication within both systems is comparable [17,18]. Information exchange between cells, called signaling pathways, follows the same principles that are required by network nodes. A message is sent to a destination and transferred, possibly using multiple hops, to this target.

From a local point of view, the information transfer works as follows. The cell expresses a specific surface molecule, the receptor. In consequence this receptor is activated, e.g. by a change in its sterical or chemical conformation (phosphorylation of defined amino acids). The activated receptor molecule is able to further activate intracellular molecules resulting in a "domino effect". The principle is not as simple as described here. Many of these signaling pathways are interfering and interacting. Different signaling molecules are affecting the same pathway. Inhibitory pathways are interfering with the straightforward signal transduction. To sum up, the final effect is dependent on the strongest signal. The effect of



0 0

Post a comment