This special section ofIEEE/ACM Transactions on Computational Biology and Bioinformaticspresents extended versions of some of the best papers accepted at the Eighth International Conference on Algorithms for Computational Biology, AlCoB 2021, held online due to the COVID-19 pandemic on November 9-11, 2021. The conference was organized by the Department of Computer Science at the University of Montana and the Institute for Research Development, Training and Advice - IRDTA, Brussels/London.

The papers in this special section were presented at the Sixth International Conference on Algorithms for Computational Biology, AlCoB 2019, that was held in Berkeley on May 28-30, 2019.

The papers in this special section were presented at the Seventh International Conference on Algorithms for Computational Biology, AlCoB 2020, held in Missoula, Montana on November 8-11, 2021 merged with AlCoB 2021. The conference was organized by the Department of Computer Science at the University of Montana and the Institute for Research Development, Training and Advice - IRDTA, Brussels/London. AlCoB 2020 was the seventh event in a series dedicated to promoting and displaying excellent research using string and graph algorithms and combinatorial optimization to deal with problems in biological sequence analysis, genome rearrangement, phylogeny reconstruction, and structure prediction.

This special section of the IEEE/ACM Transactions on Computational Biology and Bioinformatics presents extended versions of some of the best papers presented at the Fifth International Conference on Algorithms for Computational Biology, AlCoB 2018, held in Hong Kong on June 25-26, 2018. The conference was organized by the Department of Computing of Hong Kong Polytechnic University and the Research Group on Mathematical Linguistics (GRLMC) from Rovira i Virgili University, Tarragona, Spain. AlCoB 2018 was the fifth event in a series dedicated to promoting and displaying excellent research using string and graph algorithms and combinatorial optimization to deal with problems in biological sequence analysis, genome rearrangement, evolutionary trees, and structure prediction. Out of 25 submissions to the conference, 11 papers were accepted (which represents an acceptance rate of 44%). Among them, the authors of three papers were invited to submit to this special section. Each submission was reviewed by three experts and, based on their comments, the guest editors decided to accept two papers for this special section (which represents an acceptance rate of about 8% out of the submissions to the conference).

The papers in this special section were presented at the 3rd International Conference on Algorithms for Computational Biology, AlCoB 2016, that was held in Trujillo, Spain, on June 21- 22, 2016.

This special section of the IEEE/ACM Transactions on Computational Biology and Bioinformatics contains extended versions of the best papers presented at the First International Conference on Algorithms for Computational Biology (AlCoB 2014). Out of 39 submissions to the conference, only four papers representing the current state-of-the-art in their respective domains were accepted to this special section.

The hairpin completion is a newly introduced operation on formal languages, inspired by biological phenomena and by DNA-computing. In this article, we analyse a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for a possible bio-lab implementation. The variant considered here concerns the lengthening of the word that forms a hairpin structure, such that this structure is preserved, without necessarily completing the hairpin. First we present a series of language theoretic results regarding the one-step and iterated hairpin lengthening of languages from different classes of the Chomsky hierarchy. Following our biological motivation we also approach several algorithmic properties of this operation. More precisely, we propose an efficient algorithm for the recognition of the iterated hairpin lengthening of a language, and show how it can be particularized to recognize the one-step hairpin lengthening of a language; the cases when the starting language is finite, regular, linear context-free or context-free are discussed. It is worth noting that these results cannot be deduced canonically from the closure properties of the discussed classes of languages. We also propose an algorithm for computing efficiently the hairpin lengthening distance between a word and all its factors; this algorithm can be used to compute the distance between two words, or the common hairpin-lengthening ancestors of two words.

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

In this paper we discuss the following interesting question about accepting hybrid networks of evolutionary processors (AHNEP), which are a recently introduced bio-inspired computing model. The question is: how many processors are required in such a network to recognise a given language L? Two answers are proposed for the most general case, when L is a recursively enumerable language, and both answers improve on the previously known bounds. In the first case the network has a number of processors that is linearly bounded by the cardinality of the tape alphabet of a Turing machine recognising the given language L. In the second case we show that an AHNEP with a fixed underlying structure can accept any recursively enumerable language. The second construction has another useful property from a practical point of view as it includes a universal AHNEP as a subnetwork, and hence only a limited number of its parameters depend on the given language.

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.

In this paper we consider hexagonal arrays on triangular grids and introduce hexagonal local picture languages and hexagonal tiling systems defining hexagonal recognizable picture languages, motivated by an analogous study of rectangular arrays by Giammarresi and Restivo. We also introduce hexagonal Wang tiles to define hexagonal Wang systems (HWS) as a formalism to describe hexagonal picture languages. It is noticed that the family of hexagonal picture languages defined by hexagonal Wang systems and the family recognized by hexagonal tiling systems coincide. Analogous to hv-domino systems describing rectangular arrays, we define xyz-domino systems and prove that recognizable hexagonal picture languages are characterized as projections of xyz-local picture languages.

Computation not only takes place in provoked contexts of scientific experimentation, but in natural circumstances too. We are going to approach computation in natural contexts. How the nature computes? Turing machines and Chomsky grammars are rewriting systems, and the same is true for Post, Thue, Markov, Lindenmayer and other classes of axiomatic systems. If, among the whole set of natural objects, we focus natural language description, we must say that major trends in contemporary linguistics look at syntax as a rewriting process. Is rewriting unavoidable in this case, does our mind work by rewriting, does the nature compute in this way? We shall attempt to defend that the answer could be negative. The arguments will come from computability theory as well as from linguistics. First we'll formally explain the former ones, then informally the latter ones. With regard to computability theory arguments, we will see that, using the operation of adjoining, a large generative capacity is obtained. This is the case with contextual grammars. It has recently been proved that each recursively enumerable language is the quotient by a regular language of a language generated by a contextual grammar of a particular form. Thus, adjoining (paste) and quotient (cut) lead to computational universality. Recursively enumerable languages can also be characterized as the quotient by a regular language of a language generated by an insertion grammar. The same result is obtained if we take the splicing operation, a formal model of the DNA recombination. This is again a cut-and-paste operation. On the basis of the proof of this result, several further characterizations of recursively enumerable languages have been obtained. Computability theory, then, could be reconstructed without rewriting (and non-terminal symbols) and without any loss in power. Our first aim will be to show some formal aspects of such reconstruction. Later, we'll try to obtain some consequences for the future development of generative theory of natural language.