Multi-objective Optimization for Marker Panel Identification in Single-cell Data

The computational analyses of single-cell data, aimed at elucidating and characterizing the functional roles of known and putative novel cell types, are enabling a thorough understanding of the processes driving cell development and pathology progression. The isolation of specific cell types is a crucial step to perform detailed analyses but requires the identification of succinct marker panels, which include genes that refer to cell surface proteins and clusters of differentiation molecules. This still represents a challenging NP-hard computational problem, which can be tackled through global optimization techniques. In this work, we formulate the marker panel identification problem as a bi-objective optimization problem, where the first objective regards the capability of the marker panels to accurately discriminate different cell types, while the second objective is related to the number of genes to include in the panel. In particular, we compared the performance of two multi-objective optimization algorithms, as well as of Genetic Algorithms (GAs) when considering only the first objective, employing two different representations for the candidate solutions. Our results show that the multi-objective optimization algorithms are better than GAs, considering both the quality and the consistency of the obtained marker panels; moreover, the collected results point out that different representations of the candidate solutions have a relevant impact on the performance of the optimization algorithms.