Short substrings of genomic data that are responsible for biological processes, such as gene expression, are referred to as motifs. Motifs with the same function may not entirely match, due to mutation events at a few of the motif positions. Allowing for non-exact occurrences significantly complicates their discovery. Given a number of DNA strings, the motif recognition problem is the task of detecting motif instances in every given sequence without knowledge of the position of the instances or the pattern shared by these substrings. We describe a novel approach to motif recognition, and provide theoretical and experimental results that demonstrate its efficiency and accuracy. Our algorithm, MCL-WMR, builds an edge-weighted graph model of the given motif recognition problem and uses a graph clustering algorithm to quickly determine important subgraphs that need to be searched further for valid motifs. By considering a weighted graph model, we narrow the search dramatically to smaller problems that can be solved with significantly less computation. The Closest String problem is a subproblem of motif recognition, and it is NP-hard. We give a linear-time algorithm for a restricted version of the Closest String problem, and an efficient polynomial-time heuristic that solves the general problem with high probability. We initiate the study of the smoothed complexity of the Closest String problem, which in turn explains our empirical results that demonstrate the great capability of our probabilistic heuristic. Important to this analysis is the introduction of a perturbation model of the Closest String instances within which we provide a probabilistic analysis of our algorithm. The smoothed analysis suggests reasons why a well-known fixed parameter tractable algorithm solves Closest String instances extremely efficiently in practice. Although the Closest String model is robust to the oversampling of strings in the input, it is severely affected by the existence of outliers. We propose a refined model, the Closest String with Outliers problem, to overcome this limitation. A systematic parameterized complexity analysis accompanies the introduction of this problem, providing a surprising insight into the sensitivity of this problem to slightly different parameterizations. Through the application of probabilistic and combinatorial insights into the Closest String problem, we develop sMCL-WMR, a program that is much faster than its predecessor MCL-WMR. We apply and adapt sMCL-WMR and MCL-WMR to analyze the promoter regions of the canola seed-coat. Our results identify important regions of the canola genome that are responsible for specific biological activities. This knowledge may be used in the long-term aim of developing crop varieties with specific biological characteristics, such as being disease-resistant.

Packet classification plays an important role in next generation networks. Packet classification is important to fulfill the requirements for many applications including firewalls, multimedia services, intrusion detection services, and differentiated services to name just a few. Hardware solutions such as CAM/TCAM do not scale well in space. Current software-based packet classification algorithms exhibit relatively poor performance, prompting many researchers to concentrate on novel frameworks and architectures that employ both hardware and software components. In this thesis we propose two novel algorithms, Packet Classification with Incremental Update (PCIU) and Group Based Search packet classification Algorithm (GBSA), that are scalable and demonstrate excellent results in terms of preprocessing and classification. The PCIU algorithm is an innovative and efficient packet classification algorithm with a unique incremental update capability that demonstrates powerful results and is accessible for many different tasks and clients. The algorithm was further improved and made more available for a variety of applications through its implementation in hardware. Four such implementations are detailed and discussed in this thesis. A hardware accelerator based on an ESL approach, using Handel-C, resulted in a 22x faster classification than a pure software implementation running on a state of the art Xeon processor. An ASIP implementation achieved on average a 21x quicker classification. We also propose another novel algorithm, GBSA, for packet classification that is scalable, fast and efficient. On average the algorithm consumes 0.4 MB of memory for a 10k rule set. In the worst case scenario, the classification time per packet is 2 μs, and the pre-processing speed is 3M Rule/sec, based on a CPU operating at 3.4 GHz. The proposed algorithm was evaluated and compared to state-of-the-art techniques, such as RFC, HiCut, Tuple, and PCIU, using several standard benchmarks. The obtained results indicate that GBSA outperforms these algorithms in terms of speed, memory usage and pre-processing time. The algorithm, furthermore, was improved and made more accessible for a variety of applications through implementation in hardware. Three approaches using this algorithm are detailed and discussed in this thesis. The first approach was implemented using an Application Specific Instruction Processor (ASIP), while the others were pure RTL implementations using two different ESL flows (Impulse-C and Handel-C). The GBSA ASIP implementation achieved, on average, a 18x faster running speed than a pure software implementation operating on a Xeon processor. Conversely, the hardware accelerators (based on the ESL approaches) resulted in 9x faster processing.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.