Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.7
2.3
Journals
Algorithms
Special Issues
Selected Papers from the Track on Foundations of Algorithmic Computational...
share announcement

Selected Papers from the Track on Foundations of Algorithmic Computational Biology at SOFSEM 2021

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Analysis of Algorithms and Complexity Theory".

Deadline for manuscript submissions: closed (31 March 2021) | Viewed by 4525

Special Issue Editors

Dr. Riccardo Dondi

E-Mail Website
Guest Editor
Department of Literature, Philosophy, Communication Studies, University of Bergamo, 24129 Bergamo, Italy
Interests: algorithm design; computational and parameterized complexity for problems in computational biology; bioinformatics and network analysis
Special Issues, Collections and Topics in MDPI journals
Dr. Florian Sikora

E-Mail Website
Guest Editor
LAMSADE, University Paris Dauphine, 75775 Paris Cedex 16, France
Interests: algorithms; computational complexity

Special Issue Information

This Special Issue is devoted to contributions on the complexity and algorithmic novelties of problems in computational biology in conjunction with Track on Foundations of Algorithmic Computational Biology at SOFSEM 2021 (25–28 JANUARY 2020, Bozen-Bolzano, Italy, https://sofsem2021.inf.unibz.it/). It aims at displaying research using graph algorithms, string algorithms, and combinatorial optimization to deal with problems arising from biology.

Papers may be purely theoretical contributions with limited biological application or a mixture of theoretical and experimental contributions, with a relevant algorithmic part.

The track focuses on discrete algorithms (approximation algorithms, exact algorithms, fixed-parameter algorithms) and complexity results for (but not limited to) the following topics: alignment and assembly of sequences, biological networks, cancer genomics, comparative genomics, gene expression, phylogenetics, sequence analysis, and system biology.

Submissions of contributions not presented at the conference are also welcome, if related to the themes of the track.

Dr. Riccardo Dondi
Dr. Florian Sikora
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Published Papers (2 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

22 pages, 524 KiB  
Article
Sorting by Multi-Cut Rearrangements
by Laurent Bulteau, Guillaume Fertin, Géraldine Jean and Christian Komusiewicz
Algorithms 2021, 14(6), 169; https://0-doi-org.brum.beds.ac.uk/10.3390/a14060169 - 29 May 2021
Cited by 3 | Viewed by 2135
Abstract
A multi-cut rearrangement of a string S is a string S′ obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string [...] Read more.
A multi-cut rearrangement of a string S is a string S′ obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string X1·X2·X3·…·Xk·Xk+1, where X1 and Xk+1 are possibly empty, and (2) rearranging the Xis so as to obtain S′=Xπ(1)·Xπ(2)·Xπ(3)·…·Xπ(k+1), π being a permutation on 1,2,…,k+1 satisfying π(1)=1 and π(k+1)=k+1. Given two strings S and T built on the same multiset of characters from an alphabet Σ, the Sorting by Multi-Cut Rearrangements (SMCR) problem asks whether a given number ℓ of k-cut rearrangements suffices to transform S into T. The SMCR problem generalizes several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting of massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint. More precisely, we investigate its classical and parameterized complexity, as well as its approximability, in the general case or when S and T are permutations. Full article
(This article belongs to the Special Issue Selected Papers from the Track on Foundations of Algorithmic Computational Biology at SOFSEM 2021)
►▼ Show Figures

Figure 1

22 pages, 357 KiB  
Article
Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
by Martin Vu and Henning Fernau
Algorithms 2021, 14(5), 131; https://0-doi-org.brum.beds.ac.uk/10.3390/a14050131 - 22 Apr 2021
Cited by 3 | Viewed by 1748
Abstract
Insertion-deletion systems have been introduced as a formalism to model operations that find their counterparts in ideas of bio-computing, more specifically, when using DNA or RNA strings and biological mechanisms that work on these strings. So-called matrix control has been introduced to insertion-deletion [...] Read more.
Insertion-deletion systems have been introduced as a formalism to model operations that find their counterparts in ideas of bio-computing, more specifically, when using DNA or RNA strings and biological mechanisms that work on these strings. So-called matrix control has been introduced to insertion-deletion systems in order to enable writing short program fragments. We discuss substitutions as a further type of operation, added to matrix insertion-deletion systems. For such systems, we additionally discuss the effect of appearance checking. This way, we obtain new characterizations of the family of context-sensitive and the family of recursively enumerable languages. Not much context is needed for systems with appearance checking to reach computational completeness. This also suggests that bio-computers may run rather traditionally written programs, as our simulations also show how Turing machines, like any other computational device, can be simulated by certain matrix insertion-deletion-substitution systems. Full article
(This article belongs to the Special Issue Selected Papers from the Track on Foundations of Algorithmic Computational Biology at SOFSEM 2021)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-2
Back to TopTop