Multiple RNA interaction can be modeled as a problem in combinatorial optimization, where the "optimal" structure is driven by an energy-minimization-like algorithm. However, the actual structure may not be optimal in this computational sense. Moreover, it is not necessarily unique. Therefore, alternative sub-optimal solutions are needed to cover the biological ground. We present a combinatorial formulation for the Multiple RNA Interaction problem with approximation algorithms to handle various interaction patterns, which when combined with Gibbs sampling and Markov Chain Monte Carlo (MCMC), can efficiently generate a reasonable number of optimal and sub-optimal solutions. When viable structures are far from an optimal solution, exploring dependence among different parts of the interaction can increase their score and boost their candidacy for the sampling algorithm. By clustering the solutions, we identify a few representatives that are distinct enough to suggest possible alternative structures.

As an advocate of infusing various algorithmic and mathematical aspects when teaching about programming, I have come to realize that an early such practice is essential for a rounded computer science education. In this paper, I show how this can be done while focusing on one theme: Fibonacci.

We propose a new mathematical model for secondary structure in proteins. Our model is inspired by percolation theory on binary strings. What sets us apart from similar work on the subject is our attempt to deviate from a data mining approach (which is mostly the trend is science these days). Therefore, in predicting secondary structures, we make it our challenge to adhere to sequence information alone, in a non ad-hoc way, with only minimal information extracted from databases of known structures. Initial results show that our model captures some essential aspects of structure formation, notably a de novo discovery of hydrophobicity from an optimization perspective. A comparison of our prediction algorithm to similar methods shows improved performance. In addition, some evolutionary algorithms using our model exhibit convergences that are consistent with information obtained from structural biology.

Chromosomal crossover is a biological mechanism to combine parental traits. It is perhaps the first mechanism ever taught in any introductory biology class. The formulation of crossover, and resulting recombination, came about 100 years after Mendel's famous experiments. To a great extent, this formulation is consistent with the basic genetic findings of Mendel. More importantly, it provides a mathematical insight for his two laws (and corrects them). From a mathematical perspective, and while it retains similarities, genetic recombination guarantees diversity so that we do not rapidly converge to the same being. It is this diversity that made the study of biology possible. In particular, the problem of genetic mapping and linkage-one of the first efforts towards a computational approach to biology-relies heavily on the mathematical foundation of crossover and recombination. Nevertheless, as students we often overlook the mathematics of these phenomena. Emphasizing the mathematical aspect of Mendel's laws through crossover and recombination will prepare the students to make an early realization that biology, in addition to being experimental, IS a computational science. This can serve as a first step towards a broader curricular transformation in teaching biological sciences. I will show that a simple and modern treatment of Mendel's laws using a Markov chain will make this step possible, and it will only require basic college-level probability and calculus. My personal teaching experience confirms that students WANT to know Markov chains because they hear about them from bioinformaticists all the time. This entire exposition is based on three homework problems that I designed for a course in computational biology. A typical reader is, therefore, an instructional staff member or a student in a computational field (e.g., computer science, mathematics, statistics, computational biology, bioinformatics). However, other students may easily follow by omitting the mathematically more elaborate parts. I kept those as separate sections in the exposition.

The interaction of two RNA molecules is a common mechanism for many biological processes. Small interfering RNAs represent a simple example of such an interaction. But other more elaborate instances of RNA-RNA interaction exist. Therefore, algorithms that predict the structure of the RNA complex thus formed are of great interest. Most of the proposed algorithms are based on dynamic programming. RNA-RNA interaction is generally NP-complete; therefore, these algorithms (and other polynomial time algorithms for that matter) are not expected to produce optimal structures. Our goal is to characterize this suboptimality. We demonstrate the existence of constant factor approximation algorithms that are based on dynamic programming. In particular, we describe 1/2 and 2/3 factor approximation algorithms. We define an entangler and prove that 2/3 is a theoretical upper bound on the approximation factor of algorithms that produce entangler-free solutions, e.g., the mentioned dynamic programming algorithms.

We present a new iterative switching algorithm called /spl pi/-RGA for an input queued switch. In an iterative switching algorithm, each iteration matches some input and an output port for packet transmission, i.e. each iteration computes a matching, therefore, if input i is matched to output j, a packet (if any) is forwarded from i to j. The matching computed in one iteration is not necessarily maximal (more input and output ports can still be matched), and hence, the size of the matching may grow with more iterations. Therefore, multiple iterations are generally performed in each matching phase of the switch to achieve a high throughput. The reason why an iteration computes a non-maximal matching is efficiency: the matching is computed in a distributed manner without a global state of the switch. This is done using a Request Grant Accept handshake in each iteration, and we restrict our attention in This work to this family of algorithms. PIM based on T. E. Anderson et al. (1993), iSLIP based on N. McKeown (1999), iLQF and iOCF based on N. McKeown (1995), DRR based on Y. Li et al. (2000), and pDRR as stated in Fast scheduler solutions to the problems of priorities for polarized data traffic by G. Damm et al. are examples of such iterative switching algorithms found in the literature. The work on n-RGA is motivated by the assumption that the number of iterations is (possibly) limited to only one iteration, and that high throughput is to be maintained for an arbitrary traffic pattern, even with that one and only iteration. The limit to one iteration emanates from the need to make a matching phase as short as possible for the switch to scale at very high speeds. The key concept behind n-RGA is the stabilization of the matching by keeping parts of the previously computed matching. This stabilization makes it possible to maintain an eventually good size matching with one iteration only. Unlike other approaches, however, n-RGA does not maintain information about the quality of the matching. TT-RGA provides high throughput in practice under uniform and non-uniform traffic patterns with one iteration. We also prove that n-RGA provides throughput and delay guarantees with a speedup of 2 and one iteration under a constant burst traffic model.

We establish some lower bounds on the speedup required to achieve throughput for some classes of switching algorithms in a input-queued switch with virtual output queues (VOQs). We use a weak notion of throughput, which will only strengthen the results, since an algorithm that cannot achieve weak throughput cannot achieve stronger notions of throughput. We focus on priority switching algorithms, i.e., algorithms that assign priorities to VOQs and forward packets of high priority first. We show a lower bound on the speedup for two fairly general classes of priority switching algorithms: input priority switching algorithms and output priority switching algorithms. An input priority scheme prioritizes the VOQs based on the state of the input queues, while an output priority scheme prioritizes the VOQs based on their output ports. We first show that, for output priority switching algorithms, a speedup S/spl ges/2 is required to achieve weak throughput. From this, we deduce that both maximal and maximum size matching switching algorithms do not imply weak throughput unless S/spl ges/2. The bound of S/spl ges/2 is tight in all cases above, based on a result in Dai et al. Finally, we show that a speedup S/spl ges/3/2 is required for the class of input priority switching algorithms to achieve weak throughput.

We propose an efficient parallel switching architecture that requires no speedup and guarantees bounded delay. Our architecture consists of k input-output-queued switches with first-in-first-out queues, operating at the line speed in parallel under the control of a single scheduler, with k being independent of the number N of inputs and outputs. Arriving traffic is demultiplexed (spread) over the k identical switches, switched to the correct output, and multiplexed (combined) before departing from the parallel switch. We show that by using an appropriate demultiplexing strategy at the inputs and by applying the same matching at each of the k parallel switches during each cell slot, our scheme guarantees a way for cells of a flow to be read in order from the output queues of the switches, thus, eliminating the need for cell resequencing. Further, by allowing the scheduler to examine the state of only the first of the k parallel switches, our scheme also reduces considerably the amount of state information required by the scheduler. The switching algorithms that we develop are based on existing practical switching algorithms for input-queued switches, and have an additional communication complexity that is optimal up to a constant factor.