Bipartite graphs and quasipositive surfaces

We present a simple combinatorial model for quasipositive surfaces and positive braids, based on embedded bipartite graphs. As a first application, we extend the well-known duality on standard diagrams of torus links to twisted torus links. We then introduce a combinatorial notion of adjacency for bipartite graph links and discuss its potential relation with the adjacency problem for plane curve singularities.

The embryonic transcription factor stage specific activator protein contains a potent bipartite activation domain that interacts with several RNA polymerase II basal transcription factors.

Stage specific activator protein (SSAP) is a member of a newly discovered class of transcription factors that contain motifs more commonly found in RNA-binding proteins. Previously, we have shown that SSAP specifically binds to its recognition sequence in both the double strand and the single strand form and that this DNA-binding activity is localized to the N-terminal RNA recognition motif domain. Three copies of this recognition sequence constitute an enhancer element that is directly responsible for directing the transcriptional activation of the sea urchin late histone H1 gene at the midblastula stage of embryogenesis. Here we show that the remainder of the SSAP polypeptide constitutes an extremely potent bipartite transcription activation domain that can function in a variety of mammalian cell lines. This activity is as much as 3 to 5 times stronger than VP16 at activating transcription and requires a large stretch of amino acids that contain glutamine-glycine rich and serine-threonine-basic amino acid rich regions. We present evidence that SSAP's activation domain shares targets that are also necessary for activation by E1a and VP16. Finally, SSAP's activation domain is found to participate in specific interactions in vitro with the basal transcription factors TATA-binding protein, TFIIB, TFIIF74, and dTAF(II) 110.

Bipartite function of a small RNA hairpin in transcription antitermination in bacteriophage lambda.

Transcription of downstream genes in the early operons of phage lambda requires a promoter-proximal element known as nut. This site acts in cis in the form of RNA to assemble a transcription antitermination complex which is composed of lambda N protein and at least four host factors. The nut-site RNA contains a small stem-loop structure called boxB. Here, we show that boxB RNA binds to N protein with high affinity and specificity. While N binding is confined to the 5' subdomain of the stem-loop, specific N recognition relies on both an intact stem-loop structure and two critical nucleotides in the pentamer loop. Substitutions of these nucleotides affect both N binding and antitermination. Remarkably, substitutions of other loop nucleotides also diminish antitermination in vivo, yet they have no detectable effect on N binding in vitro. These 3' loop mutants fail to support antitermination in a minimal system with RNA polymerase (RNAP), N, and the host factor NusA. Furthermore, the ability of NusA to stimulate the formation of the RNAP-boxB-N complex is diminished with these mutants. Hence, we suggest that boxB RNA performs two critical functions in antitermination. First, boxB binds to N and secures it near RNAP to enhance their interaction, presumably by increasing the local concentration of N. Second, boxB cooperates with NusA, most likely to bring N and RNAP in close contact and transform RNAP to the termination-resistant state.

Structural basis for the specificity of bipartite nuclear localization sequence binding by importin-α

Importin-alpha is the nuclear import receptor that recognizes cargo proteins carrying conventional basic monopartite and bipartite nuclear localization sequences (NLSs) and facilitates their transport into the nucleus. Bipartite NLSs contain two clusters of basic residues, connected by linkers of variable lengths. To determine the structural basis of the recognition of diverse bipartite NLSs by mammalian importin-alpha, we co-crystallized a non-autoinhibited mouse receptor protein with peptides corresponding to the NLSs from human retinoblastoma protein and Xenopus laevis phosphoprotein N1N2, containing diverse sequences and lengths of the linker. We show that the basic clusters interact analogously in both NLSs, but the linker sequences adopt different conformations, whereas both make specific contacts with the receptor. The available data allow us to draw general conclusions about the specificity of NLS binding by importin-alpha and facilitate an improved definition of the consensus sequence of a conventional basic/bipartite NLS (KRX10-12KRRK) that can be used to identify novel nuclear proteins.

On the forced matching numbers of bipartite graphs

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.

The extended metamorphosis of a complete bipartite design into a cycle system

A K-t,K-t-design of order n is an edge-disjoint decomposition of K-n into copies of K-t,K-t. When t is odd, an extended metamorphosis of a K-t,K-t-design of order n into a 2t-cycle system of order n is obtained by taking (t - 1)/2 edge-disjoint cycles of length 2t from each K-t,K-t block, and rearranging all the remaining 1-factors in each K-t,K-t block into further 2t-cycles. The 'extended' refers to the fact that as many subgraphs isomorphic to a 2t-cycle as possible are removed from each K-t,K-t block, rather than merely one subgraph. In this paper an extended metamorphosis of a K-t,K-t-design of order congruent to 1 (mod 4t(2)) into a 2t-cycle system of the same order is given for all odd t > 3. A metamorphosis of a 2-fold K-t,K-t-design of any order congruent to 1 (mod 4t(2)) into a 2t-cycle system of the same order is also given, for all odd t > 3. (The case t = 3 appeared in Ars Combin. 64 (2002) 65-80.) When t is even, the graph K-t,K-t is easily seen to contain t/2 edge-disjoint cycles of length 2t, and so the metamorphosis in that case is straightforward. (C) 2004 Elsevier B.V. All rights reserved.

Components of optical qubits encoded in sideband modes

We describe a scheme for the encoding and manipulation of single photon qubits in optical sideband modes using standard optical elements. We propose and analyze the radio frequency half-wave plate, which may be used to make arbitrary rotations of a state in the frequency basis, and the frequency beamsplitter, which may be used to separate (or combine) photons of different frequencies into (from) different spatial modes.

Transmission of optical coherent-state qubits

We discuss the long-distance transmission of qubits encoded in optical coherent states. Through absorption, these qubits suffer from two main types of errors, namely the reduction of the amplitude of the coherent states and accidental application of the Pauli Z operator. We show how these errors can be fixed using techniques of teleportation and error-correcting codes.

High-fidelity Z-measurement error encoding of optical qubits

We demonstrate a quantum error correction scheme that protects against accidental measurement, using a parity encoding where the logical state of a single qubit is encoded into two physical qubits using a nondeterministic photonic controlled-NOT gate. For the single qubit input states vertical bar 0 >, vertical bar 1 >, vertical bar 0 > +/- vertical bar 1 >, and vertical bar 0 > +/- i vertical bar 1 > our encoder produces the appropriate two-qubit encoded state with an average fidelity of 0.88 +/- 0.03 and the single qubit decoded states have an average fidelity of 0.93 +/- 0.05 with the original state. We are able to decode the two-qubit state (up to a bit flip) by performing a measurement on one of the qubits in the logical basis; we find that the 64 one-qubit decoded states arising from 16 real and imaginary single-qubit superposition inputs have an average fidelity of 0.96 +/- 0.03.

Multiquantum eigenstates of a linear chain of coupled qubits

We present a technique to identify exact analytic expressions for the multiquantum eigenstates of a linear chain of coupled qubits. A choice of Hilbert subspaces is described that allows an exact solution of the stationary Schrodinger equation without imposing periodic boundary conditions and without neglecting end effects, fully including the dipole-dipole nearest-neighbor interaction between the atoms. The treatment is valid for an arbitrary coherent excitation in the atomic system, any number of atoms, any size of the chain relative to the resonant wavelength and arbitrary initial conditions of the atomic system. The procedure we develop is general enough to be adopted for the study of excitation in an arbitrary array of atoms including spin chains and one-dimensional Bose-Einstein condensates.

Loss-tolerant optical qubits

We present a linear optics quantum computation scheme that employs a new encoding approach that incrementally adds qubits and is tolerant to photon loss errors. The scheme employs a circuit model but uses techniques from cluster-state computation and achieves comparable resource usage. To illustrate our techniques we describe a quantum memory which is fault tolerant to photon loss.

Interconvertibility of single-rail optical qubits

We show how to convert between partially coherent superpositions of a single photon with the vacuum by using linear optics and postselection based on homodyne measurements. We introduce a generalized quantum efficiency for such states and show that any conversion that decreases this quantity is possible. We also prove that our scheme is optimal by showing that no linear optical scheme with generalized conditional measurements, and with one single-rail qubit input, can improve the generalized efficiency. (c) 2006 Optical Society of America.

An Algorithm for Optimal Bipartite PLA Folding

This paper presents some results of PLA area optimizing by means of its column and row folding. A more restricted type of PLA simple folding is considered. It is introduced by Egan and Liu and called as bipartite folding. An efficient approach is presented which allows finding an optimal bipartite folding without exhaustive computational efforts.