Efficient optimization algorithms for computational biology

The development of efficient optimization algorithms is crucial for computational biology due to the unique challenges and requirements of biological data. These algorithms may enable researchers to extract meaningful insights from vast and complex data sets, driving forward our understanding of biological systems and improving therapeutic interventions. In this thesis, we have developed algorithms for computational biology in cancer subtyping and drug-target interaction prediction. Identifying cancer subtypes is important for providing personalized treatment effectively, developing new drugs, characterizing risk factors, and understanding the underlying mechanisms of diseases. In the first part of this thesis, we present a clustering algorithm, named GSPS, that uses multiple kernels defined on pathways/gene sets for identifying cancer subtypes. GSPS employs an efficient decomposition algorithm for solving large scale optimization problems within the localized multiple kernel k-means clustering and provides a standalone framework for obtaining patient subtypes on cancer cohorts. We perform clustering experiments on gene expression profiles of primary tumors for 33 cancer types of the Cancer Genome Atlas using three different pathway/gene set collections. We compare our proposed method against three standard algorithms that can integrate pathway and gene expression profiles. Our approach shows statistically significantly better or comparable performance on survival analyses. Our method is also able to produce interpretable information between obtained cancer subtypes and pathway/gene set collections. In the second part of this thesis, we also propose a novel framework, manifold optimization based kernel preserving embedding (MOKPE), to efficiently solve the problem of modeling heterogeneous data. In many applications of bioinformatics, data stem from distinct heterogeneous sources. One of the well-known examples is the identification of drug-target interactions (DTIs), which is of significant importance in drug discovery and repurposing. Our model projects heterogeneous drug and target data into a unified embedding space by preserving drug-target interactions and drug-drug, target-target similarities simultaneously. We performed ten replications of ten-fold cross validation on four different drug-target interaction network data sets for predicting DTIs for previously unseen drugs. The classification evaluation metrics showed better or comparable performance compared to previous similarity-based state-of-the-art methods. We also evaluated MOKPE on predicting unknown DTIs of a given network. In this thesis, we also extended MOKPE, and developed MOKPE+, to use multiple drug-drug and target-target similarities with the aim of increasing the accuracy and interpretability of DTI predictions. For this purpose, using a localized approach, we followed a similarity selection and fusion method that has features such as estimating the similarity weights of previously unseen new drugs and cleaning noisy input. We performed ten-fold cross-validation with five replications to predict DTIs for new drugs on four different drug-target interaction network data sets. We used this similarity selection and integration method both with MOKPE+ and in the baseline models we have previously compared. We also used methods specifically developed to exploit multiple similarities. Classification evaluation metrics showed that MOKPE+ showed better or similar performance compared to both other baseline models and machine learning models that can use multiple similarities directly.