Int. J. of Innovative Computing and Applications   »   2016 Vol.7, No.3

 

 

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

 

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

 

Submission date: 10 Dec 2015
Date of acceptance: 03 Mar 2016
Available online: 18 Aug 2016

 

 

Editors Full text accessPurchase this articleComment on this article