Tag: Natural Computing

Efficient algorithms for self assembling non-rectangular nano structures

Abstract  Nano fabrication with biomolecular/DNA self assembly is a promising area of research. Building nano structures with self assembly
is both efficient and inexpensive. Soloveichik and Winfree (SIAM J Comput 36(6):1544–1569, 2007) fo…

Abstract  

Nano fabrication with biomolecular/DNA self assembly is a promising area of research. Building nano structures with self assembly
is both efficient and inexpensive. Soloveichik and Winfree (SIAM J Comput 36(6):1544–1569, 2007) formalized a two dimensional (2D) tile assembly model based on Wang’s tiling technique. Algorithms with an optimal tile
complexity of


(\Uptheta(\fraclog(N)log(log(N))))

were proposed earlier to uniquely self assemble an N × N square (with a temperature of α = 2) on this model. However efficient constructions to assemble arbitrary shapes are not
known and have remained open. In this paper we present self assembling algorithms to assemble a triangle of base 2N − 1 (units) and height N with a tile complexity of


\Uptheta(log(N)).

We also describe how this framework can be used to construct other shapes such as rhombus, hexagon etc.

  • Content Type Journal Article
  • Pages 583-594
  • DOI 10.1007/s11047-010-9210-4
  • Authors
    • Vamsi Kundeti, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA
    • Sanguthevar Rajasekaran, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA

On the computational complexity of spiking neural P systems

Abstract  It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential
time and space overheads. The spiking neural P systems considered here have a constant number of neurons t…

Abstract  

It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential
time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent
of the input length. Following this, we construct a universal spiking neural P system with exhaustive use of rules that simulates
Turing machines in linear time and has only 10 neurons.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9213-1
  • Authors
    • Turlough Neary, Boole Centre for Research in Informatics, University College Cork, Cork, Ireland

An immune-inspired approach to qualitative system identification of biological pathways

Abstract  In this paper, a special-purpose qualitative model learning (QML) system using an immune-inspired algorithm is proposed to qualitatively reconstruct biological pathways. We choose a
real-world application, the detoxification pathwa…

Abstract  

In this paper, a special-purpose qualitative model learning (QML) system using an immune-inspired algorithm is proposed to qualitatively reconstruct biological pathways. We choose a
real-world application, the detoxification pathway of Methylglyoxal (MG), as a case study. First a converter is implemented
to convert possible pathways to qualitative models. Then a general learning strategy is presented. To improve the scalability
of the proposed QML system and make it adapt to future more complicated pathways, a modified clonal selection algorithm (CLONALG)
is employed as the search strategy. The performance of this immune-inspired approach is compared with those of exhaustive
search and two backtracking algorithms. The experimental results indicate that this immune-inspired approach can significantly
improve the search efficiency when dealing with some complicated pathways with large-scale search spaces.

  • Content Type Journal Article
  • Pages 189-207
  • DOI 10.1007/s11047-010-9212-2
  • Authors
    • Wei Pang, College of Computer Science and Technology, Jilin University, Changchun, 130012 China
    • George M. Coghill, Department of Computing Science, University of Aberdeen, Aberdeen, AB24 3UE UK

Quantitative evaluation of time-dependent Petri nets and applications to biochemical networks

Abstract  Time Petri nets (TPN) are a well-known extension of standard Petri nets, where each transition gets a continuous time interval,
specifying the range of the transition’s firing time. In contrast, Timed Petri nets are a different t…

Abstract  

Time Petri nets (TPN) are a well-known extension of standard Petri nets, where each transition gets a continuous time interval,
specifying the range of the transition’s firing time. In contrast, Timed Petri nets are a different time-dependent extension
where a time duration is associated with each transition. We sketch a locally defined transformation from a Timed into a Time
Petri net. Additionally, we consider time-dependent Petri nets, where the firing of each transition lasts a certain time which
is limited by both a lower and an upper bound. These nets can also be transformed locally into TPN and are used in this paper
for modelling and analysing biochemical systems, and we present algorithms allowing their quantitative analyses. We consider
algorithms which work for arbitrary systems, i.e., bounded as well as unbounded ones, and algorithms, which are suitable for
bounded systems only. The crucial point is the state space reduction, which exploits basically two ideas: parametric state
description and discretisation of the state space. Altogether, we introduce eight problems, characterised by their input/
output relation. A sketch of the solution idea as well as possible application scenarios to evaluate biochemical systems are
given, too.

  • Content Type Journal Article
  • Pages 1017-1043
  • DOI 10.1007/s11047-010-9211-3
  • Authors
    • Louchka Popova-Zeugmann, Department of Computer Science, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany

Computational power of insertion–deletion (P) systems with rules of size two

Abstract  This article investigates insertion–deletion systems of small size, where at most two symbols can be used in the description
of insertion or deletion rules in a context-free or contextual manner. The basic result shows a characte…

Abstract  

This article investigates insertion–deletion systems of small size, where at most two symbols can be used in the description
of insertion or deletion rules in a context-free or contextual manner. The basic result shows a characterization by context-free
grammars of insertion–deletion systems, which insert or delete one symbol in one symbol left context (systems of size (1,
1, 0; 1, 1, 0)). If context-free insertion or deletion rules are considered (systems of size (2, 0, 0; 1, 1, 0) or (1, 1,
0; 2, 0, 0)), then we show that corresponding systems are not computationally complete. However, if the insertion and the
deletion operations having same size as above are considered in the distributed framework of P systems, then the computational
power strictly increases and the obtained models become computationally complete. The article also shows that if context-free
insertion and deletion rules of two symbols (of size (2, 0, 0; 2, 0, 0)) are used in combination with P systems, then the
obtained model is still not computationally complete. Finally some open problems are presented.

  • Content Type Journal Article
  • Pages 835-852
  • DOI 10.1007/s11047-010-9208-y
  • Authors
    • Alexander Krassovitskiy, Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, Tarragona, 43002 Spain
    • Yurii Rogozhin, Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, Tarragona, 43002 Spain
    • Sergey Verlan, LACL, Département Informatique, Université Paris Est, 61, av. Général de Gaulle, 94010 Créteil, France

Theoretical and computational properties of transpositions

Abstract  Transposable genetic elements are prevalent across many living organisms from bacteria to large mammals. Given the linear
primary structure of genetic material, this process is natural to study from a theoretical perspective using …

Abstract  

Transposable genetic elements are prevalent across many living organisms from bacteria to large mammals. Given the linear
primary structure of genetic material, this process is natural to study from a theoretical perspective using formal language
theory. We abstract the process of genetic transposition to operations on languages and study it combinatorially and computationally.
It is shown that the power of such systems is large relative to the classic Chomsky Hierarchy. However, we are still able
to algorithmically determine whether or not a string is a possible product of the iterated application of the operations.

  • Content Type Journal Article
  • Pages 795-804
  • DOI 10.1007/s11047-010-9207-z
  • Authors
    • Mark Daley, Departments of Computer Science and Biology, University of Western Ontario, London, ON N6A 5B7, Canada
    • Ian McQuillan, Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada
    • James M. McQuillan, Department of Computer Science, Western Illinois University, Macomb, IL 61455-1390, USA
    • Kalpana Mahalingam, Department of Computer Science, Indian Institute of Technology Madras, Chennai, 600 036 India

Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

Abstract  The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational
perspective, that is, from the perspective of mathematical problems whose study may give insight into th…

Abstract  

The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational
perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes
through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly
is the minimum tile set problem, which in the extended formulation we consider, here referred to as MTSP, asks for a collection
of types of elementary objects (called tiles) to be found for the self-assembly of an object having a pre-established shape.
Such a collection is to be as concise as possible, thus minimizing supply diversity, while satisfying a set of stringent constraints
having to do with important properties of the self-assembly process from its tile types. We present a study of what, to the
best of our knowledge, is the first practical approach to MTSP. Our study starts with the introduction of an evolutionary
heuristic to tackle MTSP and includes selected results from extensive experimentation with the heuristic on the self-assembly
of simple objects in two and three dimensions, including the possibility of tile rotation. The heuristic we introduce combines
classic elements from the field of evolutionary computation with a problem-specific variant of Pareto dominance into a multi-objective
approach to MTSP.

  • Content Type Journal Article
  • Pages 551-581
  • DOI 10.1007/s11047-010-9209-x
  • Authors
    • Fabio R. J. Vieira, Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, Rio de Janeiro, RJ 21941-972, Brazil
    • Valmir C. Barbosa, Programa de Engenharia de Sistemas e Computação, COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, Rio de Janeiro, RJ 21941-972, Brazil

An immune system inspired clustering and classification method to detect critical areas in electrical power networks

Abstract  Identifying critical, failure prone areas in a power system network are often a difficult and computationally intensive task.
Artificial Immune System (AIS) algorithms have been shown to be capable of generalization and learning to…

Abstract  

Identifying critical, failure prone areas in a power system network are often a difficult and computationally intensive task.
Artificial Immune System (AIS) algorithms have been shown to be capable of generalization and learning to identify previously
unseen patterns. In this paper, a method is developed that uses artificial immune system classification and clustering algorithms
to identify critical areas in the network. The algorithm identifies areas of the power system network that are prone to voltage
collapse and areas with overloaded lines. The applicability of AIS for this particular task is demonstrated on test electrical
power system networks. Its accuracy is compared with an optimised support vector machine (SVM) algorithm and k nearest neighbours
algorithm (kNN) across 3 different power system networks.

  • Content Type Journal Article
  • Pages 305-333
  • DOI 10.1007/s11047-010-9204-2
  • Authors
    • N. C. Woolley, School of Electrical and Electronic Engineering, The University of Manchester, Ferranti Building, Manchester, M601QD UK
    • J. V. Milanović, School of Electrical and Electronic Engineering, The University of Manchester, Ferranti Building, Manchester, M601QD UK

Selected papers of Vincenzo Manca

Selected papers of Vincenzo Manca
Content Type Journal ArticlePages 183-185DOI 10.1007/s11047-010-9202-4

Journal Natural ComputingOnline ISSN 1572-9796Print ISSN 1567-7818

Journal Volume Volume 10

Journal Issue Volume 10, Number 1

Selected papers of Vincenzo Manca

  • Content Type Journal Article
  • Pages 183-185
  • DOI 10.1007/s11047-010-9202-4

Automata and processes on multisets of communicating objects

Abstract  Inspired by P systems initiated by Gheorghe Pãun, we study a computation model over a multiset of communicating objects. The
objects in our model are instances of finite automata. They interact with each other by firing external t…

Abstract  

Inspired by P systems initiated by Gheorghe Pãun, we study a computation model over a multiset of communicating objects. The
objects in our model are instances of finite automata. They interact with each other by firing external transitions between
two objects. Our model, called a service automaton, is intended to specify, at a high level, a service provided on top of
network devices abstracted as communicating objects. We formalize the concept of processes, running over a multiset of objects,
of a service automaton and study the computing power of both single-process and multiprocess service automata. In particular,
in the multiprocess case, regular maximal parallelism is defined for inter-process synchronization. It turns out that single-process
service automata are equivalent to vector addition systems and hence can define nonregular processes. Among other results,
we also show that Presburger reachability problem for single-process service automata is decidable, while it becomes undecidable
in the multiprocess case. Hence, multiprocess service automata can not be effectively simulated by vector addition systems.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9206-0
  • Authors
    • Linmin Yang, School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA
    • Yong Wang, Google Inc., Mountain View, CA 94043, USA
    • Zhe Dang, School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA 99164, USA