Bio-Inspired Computing Models and Algorithms

Tao Song, Pan Zheng;Mou Ling Dennis Wong;Xun Wang

• Éditeur: WSPC
• Année: 2019
• ISBN:
  9789813143197
• Sujet: Informatik
• Sous-sujet: Künstliche Intelligenz (KI) & Semantik

Bio-inspired computing (BIC) focuses on the designs and developments of computer algorithms and models based on biological mechanisms and living phenomena. It is now a major subfield of natural computation that leverages on the recent advances in computer science, biology and mathematics.

The ideas provide abundant inspiration to construct high-performance computing models and intelligent algorithms, thus enabling powerful tools to solve real-life problems.

Written by world-renowned researchers, this compendium covers the most influential topics on BIC, where the newly-obtained algorithms, developments and results are introduced and elaborated. The potential and valuable directions for further research are addressed as well.

Contents:

• A Gentle Introduction to Membrane Systems and Their Computational Properties (Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E Porreca and Claudio Zandron)
• Results on Computational Complexity in Bio-inspired Computing (Mario J Pérez-Jiménez, Agustín Riscos-Núñez, Luis Valencia-Cabrera and David Orellana-Martín)
• Integrative Approaches for Predicting microRNA Function and Prioritizing Disease-Related microRNA Using Biological Interaction Networks (Xuan Zhang and Xiangxiang Zeng)
• Evolutionary Algorithm for Solving Complex Multiobjective Optimization Problems (Ye Tian and Xingyi Zhang)
• A Bio-inspired Clustering Model for Anomaly Detection in the Mining Industry (Raymond Chiong, Zhongyi Hu, Zongwen Fan, Yuqing Lin, Stefan Chalup and Antoine Desmet)
• Picture Generating Models Based on the Splicing Operation (K G Subramanian, G Samdanielthompson and N Gnanamalar David)
• Fingerprint Minutiae to Fixed-Length Bit-String: A Review of Recent Development (Zhe Jin, Wei-Jing Wong and Andrew Beng Jin Teoh)
• Platform for Detection of Ultra-DNA Signals (10–18 mol/L) with DNA Probe and Nanomaterials (Xun Wang and Ben Hoo Mook)
• Deep Autoencoders in Pattern Recognition: A Survey (Junfen Chen, Bojun Xie, Hui Zhang and Junhai Zhai)
• Genetic Algorithm: From Promiscuity to Monogamy (Ting Yee Lim and Choo Jun Tan)

Readership: Researchers, academics and professionals in artificial intelligence, neural networks, theoretical computer science, bioinformatics and biocomputing.Bio-Inspired Computing;Nature Computing;Membrane Computing;Biometric;Bioinformatics;Neural Networks;Machine Learning00

Chapter 1

A Gentle Introduction to Membrane Systems and Their Computational Properties

Alberto Leporati^∗, Luca Manzoni^†, Giancarlo Mauri^‡,
Antonio E. Porreca^§ and Claudio Zandron^¶

Dipartimento di Informatica, Sistemistica e Comunicazione
Universit à degli Studi di Milano-Bicocca
Viale Sarca 336, Building U14, 20126 Milano, Italy
^∗[email protected]
^†[email protected]
^‡[email protected]
^§[email protected]
^¶[email protected]

Membrane computing, known as a novel branch in computer science, has gain plenty of results in both theoretical and application levels. In this chapter, a gentle introduction to membrane systems and their computational properties is discussed. Membrane structures, the content of region, computation rules are recalled, as well as the formal definition of membrane systems is given. The computational power, as both generating and accepting deceives are shown, and the computational efficiency are discussed by solving computational hard problems by membrane systems.

1.1.Introduction

The theory of computation investigates the nature and properties of algorithmic procedures. This field emerged in the 1920s and 1930s of the 20th century from the work on the philosophy and the foundations of mathematics. Of great importance and inspiration was David Hilbert’s ambitious program to “dispose of the foundational questions in mathematics once and for all” [34], that led to fundamental results in logic such as Gödel’s incompleteness theorems [6], and ultimately to the birth of recursion theory (nowadays mostly referred to as computability theory) and computer science itself.

The formal notion of computability that is almost universally adopted today is due to Alan Turing, who introduced in his ground-breaking paper [32] a simple, elegant and convincing mathematical formalization of the notion of computation, as it is carried out by a human executor equipped with enough scratch paper. Turing’s work showed that, as long as we accept his notion of computation, there exist well-formed mathematical questions whose answer cannot be computed. In particular, one of the main challenges of Hilbert’s program, the Entscheidungsproblem (finding a decision procedure for the validity of statements in first-order logic) was proved to be unsolvable.

This formalization, that rapidly became known as the Turing machine, is still the reference model for computing devices in theoretical computer science, as it also enjoys the property of being a good model of actual electronic computers; this is also due to the fact that it was itself an inspiration for the design of automatic computing machinery [5].

With the development of computers as a technology, being able to solve a particular problem proved not to be satisfying: fast, efficient solutions are needed. This led to the development of computational complexity theory, pioneered [9] by Hartmanis and Stearns in [12], which also gives the name to the field. Identifying the notion of “efficient” with “polynomial-time computable” is due [9] to Edmonds [7], while the central question of complexity theory, whether P = NP, arose from the work of Cook [4] and Karp [16]. This question has shaped the whole development of the field and still remains open today.

However, the theory of computation is not entirely about Turing machines. Several authors sought to draw inspiration from the way nature “computes” in order to define alternative, unconventional computing models or, from the opposite point of view, to interpret natural phenomena as computation [1]. For instance, artificial neural networks [21] are inspired by the functioning of neurons in the brain, and genetic algorithms seek to solve computationally hard problems by simulating the processes of mutation, mating and natural selection. A clear example of biological inspiration is given by DNA computing, which provided an actual in vitro implementation of an algorithm for the Hamilton path problem [2] (the theory was initiated a few years earlier, particularly by Head [13]).

Inspired by the work on DNA computing [26], Pun introduced in 1998 (see [24]) the notion of membrane systems, initially called super-cells, and nowadays usually known as P systems. Here the computing device is an abstraction of biological cells. Unlike in neural networks, we do not deal with cells as atomic objects: as the name suggests, the focus is on the membranes that define the cells and their internal compartments, which work together by performing different individual functions. The chemical environment of the various compartments are described in terms of multisets of symbols (i.e. sets in which each symbol has a multiplicity). Another defining feature of P systems (as they were initially defined) is maximal parallelism: as many operations as possible are carried out simultaneously, and no part of the system remains inactive if it can carry out some part of the computation.

Although P systems have also been investigated from the perspectives of bioinformatics and systems biology, where they might be used as models of biological phenomena in computer simulations, most of the research in membrane computing has been carried out from a language-theoretic (including the seminal paper [24]), computability-theoretic and complexity-theoretic standpoint.

In the literature, many variants using various kinds of rules and different features have been considered and investigated in this respect. For example, the notion of multiset rewriting employed in the original model of the P system [24] is context-sensitive (or cooperative, which is the term normally used in membrane computing). Other classes of P systems, however, possess other features that make them extremely powerful from a computational perspective: as a consequence, the use of context-free (or non-cooperative) rewriting rules has also been considered. Here, for the sake of explanation, we will present a simplified model using only the basic ingredients and simple cooperative rewriting rules. After presenting some basic definitions, we will first show that such systems are Turing complete, by simulating register machines, a well-known universal computing device, and we will show that the direct simulation of Turing machines is time efficient. Then, by exploiting the possibility of creating new membranes by division of existing ones, we will show how to solve all the problems from the complexity classes NP and PSPACE in polynomial time (and exponential space) by means of membrane systems. At the end of the chapter, we will shortly discuss how cooperation can be avoided, and we will provide pointers to the literature concerning main variants considered in the framework of membrane computing.

1.2.Membrane Structures

The main feature of all variants of P systems is their membrane structure. Several variants have been proposed in the literature [27], but we consider here the original cell-like shape [24]: a hierarchy of membranes nested to an arbitrary depth. There is a clear bijective mapping between the set of membranes and the regions they define, delimited by the membrane itself from the outside, and any membrane immediately included in it from the inside. The outermost membrane (sometimes called the skin) separates the actual P system from the surrounding environment, which is a furth...

Table des matières

• Cover
• Halftitle
• Title
• Copyright
• Preface
• Contents
• Chapter 1. A Gentle Introduction to Membrane Systems and Their Computational Properties
• Chapter 2. Results on Computational Complexity in Bio-inspired Computing
• Chapter 3. Integrative Approaches for Predicting microRNA Function and Prioritizing Disease-Related microRNA Using Biological Interaction Networks
• Chapter 4. Evolutionary Algorithm for Solving Complex Multiobjective Optimization Problems
• Chapter 5. A Bio-inspired Clustering Model for Anomaly Detection in the Mining Industry
• Chapter 6. Picture Generating Models Based on the Splicing Operation
• Chapter 7. Fingerprint Minutiae to Fixed-Length Bit-String: A Review of Recent Development
• Chapter 8. Platform for Detection of Ultra-DNA Signals (10–18 mol/L) with DNA Probe and Nanomaterials
• Chapter 9. Deep Autoencoders in Pattern Recognition: A Survey
• Chapter 10. Genetic Algorithm: From Promiscuity to Monogamy
• Index