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

摘要

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.