published_or_final_version / abstract / toc / Mathematics / Master / Master of Philosophy

For as long as biologists have been computing alignments of sequences, the question of what values to use for scoring substitutions and gaps has persisted. In practice, substitution scores are usually chosen by convention, and gap penalties are often found by trial and error. In contrast, a rigorous way to determine parameter values that are appropriate for aligning biological sequences is by solving the problem of Inverse Parametric Sequence Alignment. Given examples of biologically correct reference alignments, this is the problem of finding parameter values that make the examples score as close as possible to optimal alignments of their sequences. The reference alignments that are currently available contain regions where the alignment is not specified, which leads to a version of the problem with partial examples.In this dissertation, we develop a new polynomial-time algorithm for Inverse Parametric Sequence Alignment that is simple to implement, fast in practice, and can learn hundreds of parameters simultaneously from hundreds of examples. Computational results with partial examples show that best possible values for all 212 parameters of the standard alignment scoring model for protein sequences can be computed from 200 examples in 4 hours of computation on a standard desktop machine. We also consider a new scoring model with a small number of additional parameters that incorporates predicted secondary structure for the protein sequences. By learning parameter values for this new secondary-structure-based model, we can improve on the alignment accuracy of the standard model by as much as 15% for sequences with less than 25% identity.

In this thesis, we will study a class of divisor functions: the prime symmetric functions. These are polynomials over Q in the so-called elementary prime symmetric functions, whose values lie in Z. The latter are defined on the nonnegative integers and take the values of the elementary symmetric functions applied to the multi-set of prime factors (with repetition) of an integer n. Initially we look at basic properties of prime symmetric functions, and consider analogues of questions posed for the usual sum of proper divisors function, such as those concerning perfect numbers or Aliquot sequences. We consider the inverse question of when, and in how many ways a number $n$ can be expressed as f(m) for certain prime symmetric functions f. Then we look at asymptotic formulae for the average orders of certain fundamental prime symmetric functions, such as the arithmetic function whose value at n is the sum of k-th powers of the prime divisors (with repetition) of n. For these last functions in particular, we also look at statistical results by comparing their distribution of values with the distribution of the largest prime factor dividing n. In addition to average orders, we look at the modular distribution of prime symmetric functions, and show that for a fundamental class, they are uniformly distributed over any fixed modulus. Then our focus shifts to the related area of partitions into prime powers. We compute the appropriate asymptotic formulae, and demonstrate important monotonicity properties. We conclude by looking at iteration problems for some of the simpler prime symmetric functions. In doing so, we consider the empirical basis for certain conjectures, and are left with many open problems.

In this thesis, we study a variant of the maximum cardinality matching problem known as the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned on every vertex and every edge, the goal is to maximize the assignment of positive feasible charges on the edges obeying the capacity constraints, so as to maximize the total sum of the charges. We use the primal-dual approach. We propose a combinatorial algorithm for solving the dual of the restricted primal and show that the primal-dual algorithm runs in a polynomial time. / ix, 96 leaves : ill. ; 29 cm

No description available.

No description available.

The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph coloring.In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

We generalize bistellar operations (often called flips) on simplicial manifolds to a notion of general flips on PL-spheres. We provide methods for computing the cd-index of these general flips, which is the change in the cd-index of any sphere to which the flip is applied. We provide formulas and relations among flips in certain classes, paying special attention to the classic case of bistellar flips. We also consider questions of "flip-connecticity", that is, we show that any two polytopes in certain classes can be connected via a sequence of flips in an appropriate class.

Natural products occupy a central role as the majority of currently used antibiotic and anticancer agents. Among these are type-II polyketide synthase (PKS)-derived molecules, or polyketides, which are produced by many representatives of the genus Streptomyces. Some type-II polyketides, such as the tetracyclines and the anthracycline doxorubicin, are currently employed as therapeutics. However, several polyketide molecules exhibit promising biological activity, but due to toxic side effects or solubility concerns, remain undeveloped as drugs. Gilvocarcin V (GV) (topoisomerase II inhibitor) has a novel mechanism of action: [2+2] cycloaddition to thymine residues by the 8-vinyl side chain and cross-linking of histone H. Mithramycin blocks transcription of proto-oncogenes c-myc and c-src by forming an Mg2+-coordinated homodimer in the GC-rich minor groove of DNA. The purpose of this research was to investigate the biosynthesis of several type II polyketide compounds (e.g. chrysomycin, elloramycin, and mithramycin) with the goal of improving the bioactivities of these drugs through combinatorial biosynthesis. Alteration of the glycosylation pattern of these molecules is one promising way to improve or alter the bioactivities of these molecules. To this end, an understanding of the glycosyltransferases and post-polyketide tailoring enzymatic steps involved in these biosynthetic pathways must be established. Four specific aims were established to meet these goals. In specific aim 1, the biosynthetic locus of chrysomycin A was successfully cloned and elucidated, which afforded novel biosynthetic tools. Chrysomycin monooxygenases were found to catalyze identical roles to their gilvocarcin counterparts. Cloning of deoxysugar constructs (plasmids) which could direct biosynthesis of ketosugars, NDP-D-virenose, and NDP-D-fucofuranose in foreign pathways was undertaken in specific aim 2. Finally, these “sugar” plasmids were introduced into producer organisms of elloramycin and mithramycin pathways in specific aims 3 and 4 to interrogate the endogenous glycosyltransferases in order to alter their glycosylation patterns. These experiments resulted in the successful generation of a newly glycosylated tetracenomycin, as well as premithramycin, and mithramycin analogues. In specific aim 4, a new mithramycin analogue with an altered sugar pattern rationally designed and improved structural features was generated and structurally elucidated.

Phylogenetic diversity (PD) is a measure of species biodiversity quantified by how much of an evolutionary tree is spanned by a subset of species. In this thesis, we study optimization problems that aim to find species sets with maximum PD in different scenarios, and examine random extinction models under various assumptions to predict the PD of species that will still be present in the future. Optimizing PD with Dependencies is a combinatorial optimization problem in which species form an ecological network. Here, we are interested in selecting species sets of a given size that are ecologically viable and that maximize PD. The NP-hardness of this problem is proved and it is established which special cases of the problem are computationally easy and which are computationally hard. It is also shown that it is NP-complete to decide whether the feasible solution obtained by the greedy algorithm is optimal. We formulate the optimization problem as an integer linear program and find exact solutions to the largest food web currently in the empirical literature. In addition, we give a generalization of PD that can be used for example when we do not know the true evolutionary history. Based on this measure, an optimization problem is formulated. We discuss the complexity and the approximability properties of this problem. In the generalized field of bullets model (g-FOB), species are assumed to become extinct with possibly different probabilities, and extinction events are independent. We show that under this model the distribution of future phylogenetic diversity converges to a normal distribution as the number of species grows. When extinction probabilities are influenced by some binary character on the tree, the state-based field of bullets model (s-FOB) represents a more realistic picture. We compare the expected loss of PD under this model to that under the associated g-FOB model and find that the former is always greater than or equal to the latter. It is natural to further generalize the s-FOB model to allow more than one binary character to affect the extinction probabilities. The expected future PD obtained for the resulting trait-dependent field of bullets model (t-FOB) is compared to that for the associated g-FOB model and our previous result is generalized.