Algorithmic Themes in Bioinformatics

A special issue of Algorithms (ISSN 1999-4893).

Deadline for manuscript submissions: closed (31 August 2015) | Viewed by 35282

Special Issue Editors

Dipartimento di Matematica e Informatica, University of Udine, Viale delle Scienze 206, 33100 Udine, Italy
Interests: computational molecular biology; mathematical programming; combinatorial optimization
Department of Mathematics, Computer Science and Physics, Via delle Scienze 206, 33100 Udine, Italy
Interests: algorithms for bioinformatics and computational biology; logic decision algorithms; algorithms and data-structures for compressed computation
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

Computational Biology and Bioinformatics offer a wealth of new and interesting topics to the algorithmic community. This is true not only because new technologies push data production rates to ever higher and more challenging levels, but also because both old and new computational aspects of (modern) biological problems are constantly rewritten and originally presented. The open access journal Algorithms will host a special issue on ``Algorithmic Themes in Bioinformatics'', whose aim is to offer a forum for exchanging and proposing new ideas and techniques related with the design and usage of algorithms in Bioinformatics.

The following is a (non-exhaustive) list of topics of interest:

  • Algorithms for sequence and structure alignment
  • Algorithms for pattern search in genomic sequences
  • Algorithms for sequence assembly
  • Algorithms for structural variation analysis
  • Algorithmic issues with new sequencing technologies
  • Algorithms for feature selection
  • Algorithmic issues in phylogenetic analysis and comparison
  • Algorithms and data structures for clustering of sequences and structures
  • Algorithms for protein structure prediction and analysis


Dr. Giuseppe Lancia 
Dr. Alberto Policriti
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.




Keywords

  • bioinformatics
  • sequence alignment
  • feature selection
  • protein structures
  • phylogenetic trees
  • evolutionary distances
  • next generation sequencing
  • genomic patterns
  • protein folding
  • metabolic networks

Published Papers (6 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

328 KiB  
Article
Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment
by Mohammed El-Kebir, Jaap Heringa and Gunnar W. Klau
Algorithms 2015, 8(4), 1035-1051; https://0-doi-org.brum.beds.ac.uk/10.3390/a8041035 - 18 Nov 2015
Cited by 20 | Viewed by 6782
Abstract
Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between [...] Read more.
Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. We present a method for global network alignment that is fast and robust and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. We exploit that network alignment is a special case of the well-studied quadratic assignment problem (QAP). We focus on sparse network alignment, where each node can be mapped only to a typically small subset of nodes in the other network. This corresponds to a QAP instance with a symmetric and sparse weight matrix. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the open source software tool Natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative established and recent state-of-the-art methods. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Graphical abstract

615 KiB  
Article
An Integer Linear Programming Formulation for the Minimum Cardinality Segmentation Problem
by Daniele Catanzaro and Céline Engelbeen
Algorithms 2015, 8(4), 999-1020; https://0-doi-org.brum.beds.ac.uk/10.3390/a8040999 - 11 Nov 2015
Cited by 2 | Viewed by 4301
Abstract
In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set [...] Read more.
In this article, we investigate the Minimum Cardinality Segmentation Problem (MCSP), an NP-hard combinatorial optimization problem arising in intensity-modulated radiation therapy. The problem consists in decomposing a given nonnegative integer matrix into a nonnegative integer linear combination of a minimum cardinality set of binary matrices satisfying the consecutive ones property. We show how to transform the MCSP into a combinatorial optimization problem on a weighted directed network and we exploit this result to develop an integer linear programming formulation to exactly solve it. Computational experiments show that the lower bounds obtained by the linear relaxation of the considered formulation improve upon those currently described in the literature and suggest, at the same time, new directions for the development of future exact solution approaches to the problem. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Figure 1

604 KiB  
Article
Automatic Classification of Protein Structure Using the Maximum Contact Map Overlap Metric
by Rumen Andonov, Hristo Djidjev, Gunnar W. Klau, Mathilde Le Boudic-Jamin and Inken Wohlers
Algorithms 2015, 8(4), 850-869; https://0-doi-org.brum.beds.ac.uk/10.3390/a8040850 - 09 Oct 2015
Cited by 2 | Viewed by 5684
Abstract
In this work, we propose a new distance measure for comparing two protein structures based on their contact map representations. We show that our novel measure, which we refer to as the maximum contact map overlap (max-CMO) metric, satisfies all properties of a [...] Read more.
In this work, we propose a new distance measure for comparing two protein structures based on their contact map representations. We show that our novel measure, which we refer to as the maximum contact map overlap (max-CMO) metric, satisfies all properties of a metric on the space of protein representations. Having a metric in that space allows one to avoid pairwise comparisons on the entire database and, thus, to significantly accelerate exploring the protein space compared to no-metric spaces. We show on a gold standard superfamily classification benchmark set of 6759 proteins that our exact k-nearest neighbor (k-NN) scheme classifies up to 224 out of 236 queries correctly and on a larger, extended version of the benchmark with 60; 850 additional structures, up to 1361 out of 1369 queries. Our k-NN classification thus provides a promising approach for the automatic classification of protein structures based on flexible contact map overlap alignments. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Figure 1

498 KiB  
Article
Finding Supported Paths in Heterogeneous Networks
by Guillaume Fertin, Christian Komusiewicz, Hafedh Mohamed-Babou and Irena Rusu
Algorithms 2015, 8(4), 810-831; https://0-doi-org.brum.beds.ac.uk/10.3390/a8040810 - 09 Oct 2015
Cited by 3 | Viewed by 5383
Abstract
Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each [...] Read more.
Subnetwork mining is an essential issue in the analysis of biological, social and communication networks. Recent applications require the simultaneous mining of several networks on the same or a similar vertex set. That is, one searches for subnetworks fulfilling different properties in each input network. We study the case that the input consists of a directed graph D and an undirected graph G on the same vertex set, and the sought pattern is a path P in D whose vertex set induces a connected subgraph of G. In this context, three concrete problems arise, depending on whether the existence of P is questioned or whether the length of P is to be optimized: in that case, one can search for a longest path or (maybe less intuitively) a shortest one. These problems have immediate applications in biological networks and predictable applications in social, information and communication networks. We study the classic and parameterized complexity of the problem, thus identifying polynomial and NP-complete cases, as well as fixed-parameter tractable and W[1]-hard cases. We also propose two enumeration algorithms that we evaluate on synthetic and biological data. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Figure 1

779 KiB  
Article
Modified Classical Graph Algorithms for the DNA Fragment Assembly Problem
by Guillermo M. Mallén-Fullerton, J. Emilio Quiroz-Ibarra, Antonio Miranda and Guillermo Fernández-Anaya
Algorithms 2015, 8(3), 754-773; https://0-doi-org.brum.beds.ac.uk/10.3390/a8030754 - 10 Sep 2015
Cited by 4 | Viewed by 5486
Abstract
DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear [...] Read more.
DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear time complexity, a heap with constant time operations was developed, for the special case where the edge weights are integers and do not depend on the problem size. The experiments presented show that modified classical graph theoretical algorithms can solve the DNA fragment assembly problem efficiently. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Figure 1

405 KiB  
Article
On String Matching with Mismatches
by Marius Nicolae and Sanguthevar Rajasekaran
Algorithms 2015, 8(2), 248-270; https://0-doi-org.brum.beds.ac.uk/10.3390/a8020248 - 26 May 2015
Cited by 7 | Viewed by 6968
Abstract
In this paper, we consider several variants of the pattern matching with mismatches problem. In particular, given a text \(T=t_1 t_2\cdots t_n\) and a pattern \(P=p_1p_2\cdots p_m\), we investigate the following problems: (1) pattern matching with mismatches: for every \(i, 1\leq i \leq [...] Read more.
In this paper, we consider several variants of the pattern matching with mismatches problem. In particular, given a text \(T=t_1 t_2\cdots t_n\) and a pattern \(P=p_1p_2\cdots p_m\), we investigate the following problems: (1) pattern matching with mismatches: for every \(i, 1\leq i \leq n-m+1\) output, the distance between \(P\) and \(t_i t_{i+1}\cdots t_{i+m-1}\); and (2) pattern matching with \(k\) mismatches: output those positions \(i\) where the distance between \(P\) and \(t_i t_{i+1}\cdots t_{i+m-1}\) is less than a given threshold \(k\). The distance metric used is the Hamming distance. We present some novel algorithms and techniques for solving these problems. We offer deterministic, randomized and approximation algorithms. We consider variants of these problems where there could be wild cards in either the text or the pattern or both. We also present an experimental evaluation of these algorithms. The source code is available at http://www.engr.uconn.edu/\(\sim\)man09004/kmis.zip. Full article
(This article belongs to the Special Issue Algorithmic Themes in Bioinformatics)
Show Figures

Figure 1

Back to TopTop