Application of combinatorial analysis to repetitions in strings, phylogeny, and parallel multiplier design
Paul Stelling · 1996
In this dissertation we apply combinatorial analysis to three problems, two motivated by biological applications and one by hardware design. First we bound the number of repetitions of primitive bases in a string of length n. The problem of finding all of the repetitions of primitive bases in a string is important for a number of applications. We bound the number of such repetitions by 1.45(n + 1)log $n-3.3n + 5.87$ by showing that the maximum number of repetitions of primitive bases that begin at position i of a string of length n is $\Theta$(log($n-i + 1)),$ with constant $\approx$1.45. We next address the biologically motivated problem of reconstructing evolutionary trees using approximate information about the descendant (leaf) species. Our approach is to use 3-way Total Order Model (TOM) information about the distances between the leaves, i.e., for all leaf triples x, y, and z, we can determine an ordering on the distances between them. An $O(n\sp3)$ time algorithm that uses TOM results for reconstructing unweighted trees when all internal nodes have degree three has been given by Kannan and Warnow. We describe a new algorithm that uses additional information to reconstruct more general trees where the only restriction is that no internal node has degree two. We also show that there are cases where the TOM test results are by themselves consistent with more than one tree. The third problem relates to the hardware design issue of constructing optimal parallel multipliers. We present new design and analysis techniques for the synthesis of fast parallel multiplier circuits. Oklobdzija, Villeger, and Lui suggested a new approach, the Three Dimensional Method (TDM), for Partial Product Reduction Reduction Tree (PPRT) design that produces multipliers which outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders by carefully modelling the relationship of the output delays to the input delays in an adder, and then interconnecting the adders in a globally optimal way. Oklobdzija, et al. suggested a heuristic for finding good PPRT designs, but no proofs about its performance were given. We formally characterize optimal TDM PPRT circuits and prove a number of properties about them. Our techniques allow us to prove tight lower bounds on multiplier circuit delays. These results are combined to create a program which finds optimal TDM multiplier designs.