Title: The maximum similarity partitioning problem and its application in the transcriptome reconstruction and quantification problem

Authors: Alex Z. Zaccaron; Said S. Adi; Carlos H.A. Higa; Eloi Araujo

Addresses: Faculty of Computation, Federal University of Mato Grosso do Sul, Brazil ' Faculty of Computation, Federal University of Mato Grosso do Sul, Brazil ' Faculty of Computation, Federal University of Mato Grosso do Sul, Brazil ' Faculty of Computation, Federal University of Mato Grosso do Sul, Brazil

Abstract: Reconstruct and quantify the RNA molecules in a cell at a given moment is an important problem in molecular biology that allows one to know which genes are being expressed and at which intensity level. Such problem is known as transcriptome reconstruction and quantification problem (TRQP). Although several approaches were already designed for the TRQP, none of them model it as a combinatorial optimisation problem over strings. In order to narrow this gap, we present here a new combinatorial optimisation problem called maximum similarity partitioning problem (MSPP) that models the TRQP. In addition, we prove that the MSPP is NP-complete in the strong sense and present a greedy heuristic for it and some experimental results.

Keywords: transcriptome reconstruction; maximum similarity partitioning; transcriptome quantification; RNA molecules; gene expression; molecular biology; TRQP; modelling; combinatorial optimisation; strings; greedy heuristics.

DOI: 10.1504/IJICA.2016.078727

International Journal of Innovative Computing and Applications, 2016 Vol.7 No.3, pp.147 - 152

Received: 17 Dec 2015
Accepted: 03 Mar 2016

Published online: 01 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article