A Netform System for Resource Planning in the U.S. Bureau of Land Management

We report an effective model and solution procedure for a major resource management problem of the U.S. Bureau of Land Management (B.L.M.), enabling large practical applications to be solved 20-300 times faster than previously possible. The resulting system has proved a useful analysis tool, providing model interaction capabilities that are employed routinely by the B.L.M. an average of 700 times a month throughout the U.S.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

General Purpose Heuristics for Integer Programming—Part II

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We provide a theoretical framework and associated explicit proposals for generating general purpose IP heuristics. Our development, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

Lewis acid-catalyzed rearrangement of 2,2-dichloronorbornane to 1-chloronorbornane

The mechanism for the unusual AlCl(3)-catalyzed rearrangement of 2,2-dichloronorbornane to 1-chloronorbornane in pentane has been elucidated; the reaction, which also yields four isomeric dichloronorbornanes, occurs in three steps: (1). ionization to form the 2-chloro-2-norbornyl cation, which was fully characterized by two-dimensional (1)H and (13)C NMR in SbF(5)/SO(2)ClF; (2). Wagner-Meerwein shift to yield the 1-chloro-2-norbornyl cation, which was partially characterized by (1)H NMR; and (3). hydride abstraction.     

Chemoenzymatic synthesis of glycopeptides with PglB, a bacterial oligosaccharyl transferase from Campylobacter jejuni

The gram-negative bacterium Campylobacter jejuni has a general N-linked glycosylation pathway encoded by the pgl gene cluster. One of the proteins in this cluster, PgIB, is thought to be the oligosaccharyl transferase due to its significant homology to Stt3p, a subunit of the yeast oligosaccharyl transferase complex. PgIB has been shown to be involved in catalyzing the transfer of an undecaprenyl-linked heptasaccharide to the asparagine side chain of proteins at the Asn-X-Ser/Thr motif. Using a synthetic disaccharide glycan donor (GaINAc-alpha1,3-bacillosamine-pyrophosphate-undecaprenyl) and a peptide acceptor substrate (KDFNVSKA), we can observe the oligosaccharyl transferase activity of PgIB in vitro. Furthermore, the preparation of additional undecaprenyl-linked glycan variants reveals the ability of PgIB to transfer a wide variety of saccharides. With the demonstration of PgIB activity in vitro, fundamental questions surrounding the mechanism of N-linked glycosylation can now be addressed.     

Eukaryotic Selenocysteine Incorporation: Mechanistic Insights

Cotranslational insertion of selenocysteine occurs in both prokaryotic and eukaryotic organisms. For the most part, what is known about this process in eukaryotes has been derived from extensive analysis of the RNA requirements for selenocysteine incorporation. Studies which have defined the selenocysteine insertion sequence (SECIS) element, identified its critical sequence and structural motifs, and established constraints on its spatial relationship with the UGA selenocysteine codon, have given mechanistic insights into this critical process.