Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

Parallel min-cut placement on reduced hardware SIMD architecture.

Massively parallel SIMD computing is applied to obtain an order of magnitude improvement in the executional speed of an important algorithm in VLSI design automation. The physical design of a VLSI circuit involves logic module placement as a subtask. The paper is concerned with accelerating the well known Min-cut placement technique for logic cell placement. The inherent parallelism of the Min-cut algorithm is identified, and it is shown that a parallel machine based on the efficient execution of the placement procedure.

Nucleotide sequence of the 3terminal region of belladonna mottle virus (renamed Physalis mottle virus) RNA and analysis of the evolutionary relationships among tymoviral coat proteins

The 3' terminal 1255 nt sequence of Physalis mottle virus (PhMV) genomic RNA has been determined from a set of overlapping cDNA clones. The open reading frame (ORF) at the 3' terminus corresponds to the amino acid sequence of the coat protein (CP) determined earlier except for the absence of the dipeptide, Lys-Leu, at position 110-111. In addiition, the sequence upstream of the CP gene contains the message coding for 178 amino acid residues of the C-terminus of the putative replicase protein (RP). The sequence downstream of the CP gene contains an untranslated region whose terminal 80 nucleotides can be folded into a characteristic tRNA-like structure. A phylogenetic tree constructed after aligning separately the sequence of the CP, the replicase protein (RP) and the tRNA-like structure determined in this study with the corresponding sequences of other tymoviruses shows that PhMV wrongly named belladonna mottle virus [BDMV(I)] is a separate tymovirus and not another strain of BDMV(E) as originally envisaged. The phylogenetic tree in all the three cases is identical showing that any subset of genomic sequence of sufficient length can be used for establishing evolutionary relationships among tymoviruses.

Visualisation of a 2′-5′ parallel stranded double helix at atomic resolution: crystal structure of cytidylyl-2′,5′-adenosine

X-ray crystallographlc studies on 3′–5′ ollgomers have provided a great deal of information on the stereochemistry and conformational flexibility of nucleic acids and polynucleotides. In contrast, there is very little Information available on 2′–5′ polynucleotides. We have now obtained the crystal structure of Cytidylyl-2′,5′-Adenoslne (C2′p5′A) at atomic resolution to establish the conformational differences between these two classes of polymers. The dlnucleoside phosphate crystallises in the monocllnlc space group C2, with a = 33.912(4)Å, b =16.824(4)Å, c = 12.898(2)Å and 0 = 112.35(1) with two molecules in the asymmetric unit. Spectacularly, the two independent C2′p5′A molecules in the asymmetric unit form right handed miniature parallel stranded double helices with their respective crystallographic two fold (b axis) symmetry mates. Remarkably, the two mini duplexes are almost indistinguishable. The cytosines and adenines form self-pairs with three and two hydrogen bonds respectively. The conformation of the C and A residues about the glycosyl bond is anti same as in the 3′–5′ analog but contrasts the anti and syn geometry of C and A residues in A2′p5′C. The furanose ring conformation is C3′endo, C2′endo mixed puckering as in the C3′p5′A-proflavine complex. A comparison of the backbone torsion angles with other 2′–5′ dinucleoside structures reveals that the major deviations occur in the torsion angles about the C3′–C2′ and C4′-C3′ bonds. A right-handed 2′–5′ parallel stranded double helix having eight base pairs per turn and 45° turn angle between them has been constructed using this dinucleoside phosphate as repeat unit. A discussion on 2′–5′ parallel stranded double helix and its relevance to biological systems is presented.

Effect of coordinated ions on structure and flexiblity of parallel G-quandruplexes: a molecular dynamics study

Single tract guanine residues can associate to form stable parallel quadruplex structures in the presence of certain cations. Nanosecond scale molecular dynamics simulations have been performed on fully solvated fibre model of parallel d(G7) quadruplex structures with Na+ or K+ ions coordinated in the cavity formed by the 06 atoms of the guanine bases. The AMBER 4.1 force field and Particle Mesh Ewald technique for electrostatic interactions have been used in all simulations. These quadruplex structures are stable during the simulation, with the middle four base tetrads showing root mean square deviation values between 0.5 to 0.8 A from the initial structure as well the high resolution crystal structure. Even in the absence of any coordinated ion in the initial structure, the G-quadruplex structure remains intact throughout the simulation. During the 1.1 ns MD simulation, one Na+ counter ion from the solvent as well as several water molecules enter the central cavity to occupy the empty coordination sites within the parallel quadruplex and help stabilize the structure. Hydrogen bonding pattern depends on the nature of the coordinated ion, with the G-tetrad undergoing local structural variation to accommodate cations of different sizes. In the absence of any coordinated ion, due to strong mutual repulsion, 06 atoms within G-tetrad are forced farther apart from each other, which leads to a considerably different hydrogen bonding scheme within the G-tetrads and very favourable interaction energy between the guanine bases constituting a G-tetrad. However, a coordinated ion between G-tetrads provides extra stacking energy for the G-tetrads and makes the quadruplex structure more rigid. Na+ ions, within the quadruplex cavity, are more mobile than coordinated K+ ions. A number of hydrogen bonded water molecules are observed within the grooves of all quadruplex structures

A systolic algorithm for hidden surface removal

With the advent of VLSI it has become possible to map parallel algorithms for compute-bound problems directly on silicon. Systolic architecture is very good candidate for VLSI implementation because of its regular and simple design, and regular communication pattern. In this paper, a systolic algorithm and corresponding systolic architecture, a linear systolic array, for the scanline-based hidden surface removal problem in three-dimensional computer graphics have been proposed. The algorithm is based on the concept of sample spans or intervals. The worst case time taken by the algorithm is O(n), n being the number of segments in a scanline. The time taken by the algorithm for a given scene depends on the scene itself, and on an average considerable improvement over the worst case behaviour is expected. A pipeline scheme for handling the I/O process has also been proposed which is suitable for VLSI implementation of the algorithm.

Boxicity of Leaf Powers

The boxicity of a graph G, denoted as boxi(G), is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, boxi(G) a parts per thousand currency sign k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.

Molecular dynamics simulations on parallel and antiparallel C.G*G triplexes

Molecular dynamics (MD) studies have been carried out on the Hoogsteen hydrogen bonded parallel and the reverse Hoogsteen hydrogen banded antiparallel C.G*G triplexes. Earlier, the molecular mechanics studies had shown that the parallel structure was energetically more favourable than the antiparallel structure. To characterize the structural stability of the two triplexes and to investigate whether the antiparallel structure can transit to an energetically more favourable structure, due to the local fluctuations in the structure during the MD simulation, the two structures were subjected to 200ps of constant temperature vacuum MD simulations at 300K. Initially no constraints were applied to the structures and it was observed that for the antiparallel tripler, the structure showed a large root mean square deviation from the starting structure within the first 12ps and the N4-H41-O6 hydrogen bond in the WC duplex got distorted due to a high propeller twist and a moderate increase in the opening angle in the basepairs. Starting from an initial value of 30 degrees, helical twist of the average structure from this simulation had a value of 36 degrees, while the parallel structure stabilized at a twist of 33 degrees. In spite of the hydrogen bond distortions in the antiparallel tripler, it was energetically comparable to the parallel tripler. To examine the structural characteristics of an undistorted structure, another MD simulation was performed on the antiparallel tripler by constraining all the hydrogen bonds. This structure stabilized at an average twist of 33 degrees. In the course of the dynamics though the energy of the molecule - compared to the initial structure - improved, it did not become comparable to the parallel structure. Energy minimization studies performed in the presence of explicit water and counterions also showed the two structures to be equally favourable energetically Together these results indicate that the parallel C.G*G tripler with Hoogsteen hydrogen bonds also represents a stereochemically and energetically favourable structure for this class of triplexes.

A Parallel Progressive Refinement Image Rendering Algorithm on a Scalable Multithreaded VLSI Processor Array

In this paper we develop a multithreaded VLSI processor linear array architecture to render complex environments based on the radiosity approach. The processing elements are identical and multithreaded. They work in Single Program Multiple Data (SPMD) mode. A new algorithm to do the radiosity computations based on the progressive refinement approach[2] is proposed. Simulation results indicate that the architecture is latency tolerant and scalable. It is shown that a linear array of 128 uni-threaded processing elements sustains a throughput close to 0.4 million patches/sec.

Dual-DSP system for signal and image processing

The design of a dual-DSP microprocessor system and its application for parallel FFT and two-dimensional convolution are explained. The system is based on a master-salve configuration. Two ADSP-2101s are configured as slave processors and a PC/AT serves as the master. The master serves as a control processor to transfer the program code and data to the DSPs. The system architecture and the algorithms for the two applications, viz. FFT and two-dimensional convolutions, are discussed.

Decentralized Parallel Operation of Inverters Sharing Unbalanced and Nonlinear Loads

In this paper, a wireless control strategy for parallel operation of three-phase four-wire inverters is proposed. A generalized situation is considered where the inverters are of unequal power ratings and the loads are nonlinear and unbalanced in nature. The proposed control algorithm exploits the potential of sinusoidal domain proportional+multiresonant controller ( in the inner voltage regulation loop) to make the system suitable for nonlinear and unbalanced loads with a simple and generalized structure of virtual output-impedance loop. The decentralized operation is achieved by using three-phase P/Q droop characteristics. The overall control algorithm helps to limit the harmonic contents and the degree of unbalance in the output-voltage waveform and to achieve excellent power-sharing accuracy in spite of mismatch in the inverter output impedances. Moreover, a synchronized turn on with consequent change over to the droop mode is applied for the new incoming unit in order to limit the circulating current completely. The simulation and experimental results from-1 kVA and -0.5 kVA paralleled units validate the effectiveness of the scheme.

Minimizing total completion time on batch processing machines

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burn-in operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.

Modelling and analysis of the variance in parallelism in parallel computations

In this paper, we introduce an analytical technique based on queueing networks and Petri nets for making a performance analysis of dataflow computations when executed on the Manchester machine. This technique is also applicable for the analysis of parallel computations on multiprocessors. We characterize the parallelism in dataflow computations through a four-parameter characterization, namely, the minimum parallelism, the maximum parallelism, the average parallelism and the variance in parallelism. We observe through detailed investigation of our analytical models that the average parallelism is a good characterization of the dataflow computations only as long as the variance in parallelism is small. However, significant difference in performance measures will result when the variance in parallelism is comparable to or higher than the average parallelism.

Compiler-assisted power optimization for clustered VLIW architectures

Clustered VLIW architectures solve the scalability problem associated with flat VLIW architectures by partitioning the register file and connecting only a subset of the functional units to a register file. However, inter-cluster communication in clustered architectures leads to increased leakage in functional components and a high number of register accesses. In this paper, we propose compiler scheduling algorithms targeting two previously ignored power-hungry components in clustered VLIW architectures, viz., instruction decoder and register file. We consider a split decoder design and propose a new energy-aware instruction scheduling algorithm that provides 14.5% and 17.3% benefit in the decoder power consumption on an average over a purely hardware based scheme in the context of 2-clustered and 4-clustered VLIW machines. In the case of register files, we propose two new scheduling algorithms that exploit limited register snooping capability to reduce extra register file accesses. The proposed algorithms reduce register file power consumption on an average by 6.85% and 11.90% (10.39% and 17.78%), respectively, along with performance improvement of 4.81% and 5.34% (9.39% and 11.16%) over a traditional greedy algorithm for 2-clustered (4-clustered) VLIW machine. (C) 2010 Elsevier B.V. All rights reserved.