Topics in parallel computation and motif discovery in bioinformatics

The following thesis addresses three problems that involve the design of algorithms which solve the following problems: (1) Routing, Selection and specific versions of Sorting in a parallel model called the Partitioned Optical Passive Star Network (POPS). The algorithms which are proposed are time optimal or near time optimal and involve the use of randomization techniques. (2) The Planted (l, d) Motif Problem. This problem arises in the context of searching transcription factor binding sites in genomic information. Our algorithms address practical and challenging instances of such problem. We implement these ideas and show that they perform better in practice when compared with already existing methods. (3) The Specific Selection Problem. This problem arises in the bioinformatics context, trying to select siRNA sequences in complete mRNA information, such that they minimize off-target hybridization. We propose and implement algorithms that address practical instances of such a problem and that achieve significant speedup over existing approaches.