Algorithms for sequence analysis via mutagenesis

Despite many successes of conventional DNA sequencing methods, some DNAs remain difficult or impossible to sequence. Unsequenceable regions occur in the genomes of many biologically important organisms, including the human genome. Such regions range in length from tens to millions of bases, and may contain valuable information such as the sequences of important genes. The authors have recently developed a technique that renders a wide range of problematic DNAs amenable to sequencing. The technique is known as sequence analysis via mutagenesis (SAM). This paper presents a number of algorithms for analysing and interpreting data generated by this technique.

Constructing and Deconstructing Latin Trades

This paper discusses existence results for latin trades and provides a Glueing Construction which is subsequently used to construct all latin trades of finite order greater than three.

Equational Reasoning as a Tool for Data Analysis

A combination of deductive reasoning, clustering, and inductive learning is given as an example of a hybrid system for exploratory data analysis. Visualization is replaced by a dialogue with the data.

Unlocking hidden genomic sequence

Despite the success of conventional Sanger sequencing, significant regions of many genomes still present major obstacles to sequencing. Here we propose a novel approach with the potential to alleviate a wide range of sequencing difficulties. The technique involves extracting target DNA sequence from variants generated by introduction of random mutations. The introduction of mutations does not destroy original sequence information, but distributes it amongst multiple variants. Some of these variants lack problematic features of the target and are more amenable to conventional sequencing. The technique has been successfully demonstrated with mutation levels up to an average 18% base substitution and has been used to read previously intractable poly(A), AT-rich and GC-rich motifs.

Common multiples of complete graphs

A graph H is said to divide a graph G if there exists a set S of subgraphs of G, all isomorphic to H, such that the edge set of G is partitioned by the edge sets of the subgraphs in S. Thus, a graph G is a common multiple of two graphs if each of the two graphs divides G.

Gauge fields, geometric phases, and quantum adiabatic pumps

Quantum adiabatic pumping of charge and spin between two reservoirs (leads) has recently been demonstrated in nanoscale electronic devices. Pumping occurs when system parameters are varied in a cyclic manner and sufficiently slowly that the quantum system always remains in its ground state. We show that quantum pumping has a natural geometric representation in terms of gauge fields (both Abelian and non-Abelian) defined on the space of system parameters. Tunneling from a scanning tunneling microscope tip through a magnetic atom could be used to demonstrate the non-Abelian character of the gauge field.

Superconducting Correlations in Metallic Nanoparticles: Exact Solution of the BCS Model by the Algebraic Bethe Ansatz

Superconducting pairing of electrons in nanoscale metallic particles with discrete energy levels and a fixed number of electrons is described by the reduced Bardeen, Cooper, and Schrieffer model Hamiltonian. We show that this model is integrable by the algebraic Bethe ansatz. The eigenstates, spectrum, conserved operators, integrals of motion, and norms of wave functions are obtained. Furthermore, the quantum inverse problem is solved, meaning that form factors and correlation functions can be explicitly evaluated. Closed form expressions are given for the form factors and correlation functions that describe superconducting pairing.

Decomposing complete tripartite graphs into cycles of lengths 3 and 4

Necessary and sufficient conditions are given for the edge-disjoint decomposition of a complete tripartite graph K-r,K-s,K-t into exactly alpha 3-cycles and beta 4-cycles. (C) 1999 Elsevier Science B.V. All rights reserved.

Maximal sets of Hamilton cycles in Kn,n

In this article, we prove that there exists a maximal set of m Hamilton cycles in K-n,K-n if and only if n/4 < m less than or equal to n/2. (C) 2000 John Wiley & Sons, Inc.

Maximum packings of K-v-K-u with triples

We construct, for all positive integers u, and v with u less than or equal to v, a decomposition of K-v - K-u (the complete graph on v vertices with a. hole of size u) into the maximum possible number of edge disjoint triangles.

The number of 4-cycles in 2-factorizations of K2n minus a 1-factor

In this paper we give a complete solution to problem of determining the number of 4-cycles in a 2-factorization of K-2n\ 1-factor. (C) 2000 Elsevier Science B.V. All rights reserved.

The line structure of balanced ternary designs with block size three, index three and rho(2) = 1, 2

In this paper necessary and sufficient conditions for a vector to be the fine structure of a balanced ternary design with block size 3, index 3 and rho(2) = 1 and 2 are determined with one unresolved case.

Decompositions of complete multipartite graphs into cycles of even length

Necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into even length cycles are investigated. Necessary conditions are listed and sufficiency is shown for the cases when the cycle length is 4, 6 or 8. Further results concerning sufficiency, provided certain small decompositions exist, are also given for arbitrary even cycle lengths.