Date of Award

2008

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Applied sciences, Biological sciences

Supervisor

Alioune Ngom

Rights

info:eu-repo/semantics/openAccess

Abstract

RNA interference (RNAi) is a highly evolutionally conserved process of post-transcriptional gene silencing (PTGS) by which double stranded RNA (dsRNA), when introduced into a cell, causes sequence-specific degradation of homologous mRNA sequences, siRNA (small interfering RNA are a class of 20-25 nucleotide-long double-stranded RNA molecules) is involved in the RNA interference (RNAi) pathway where the siRNA interferes with the expression of a specific gene. We focus on the problem of gene family knockdown by using the minimal number of siRNAs. The problem is to determine the minimal number of siRNAs required to knockdown a family of genes targeted by these siRNAs. This is a minimal set covering problem, and hence it is NP-hard. In this thesis, we explore a number of heuristic optimization methods for the minimal siRNA covering problem. Such methods include evolutionary heuristics, as well as novel greedy methods, applied for the first time to the minimal siRNA cover problem. Preliminary experiments with genetic algorithms show significant reduction in the siRNA cover size, when compared with branch & bound and probabilistic greedy. We are currently implementing novel greedy methods which are variants of well-known feature subset selection algorithms. In such methods, we define criterion functions over a collection of siRNA subsets to help us decide which subset is best to be included in a candidate solution.

We use three gene families: the FREP genes from Biomphalaria glabrata and the olfactory genes from Caenorhabditis elegans. We also conducted experiments on one artificial data set.

Download

Share

COinS