Generation of RNA pseudoknot structures with topological genus filtration

In this paper we present a sampling framework for RNA structures of fixed topological genus. We introduce a novel, linear time, uniform sampling algorithm for RNA structures of fixed topological genus g  , for arbitrary g>0$g>0$. Furthermore we develop a linear time sampling algorithm for RNA structures of fixed topological genus g   that are weighted by a simplified, loop-based energy functional. For this process the partition function of the energy functional has to be computed once, which has O(n²)$O(n^2)$ time complexity.     

Learning Probabilistic Features for Robotic Navigation Using Laser Sensors

SLAM is a popular task used by robots and autonomous vehicles to build a map of an unknown environment and, at the same time, to determine their location within the map. This paper describes a SLAM-based, probabilistic robotic system able to learn the essential features of different parts of its environment. Some previous SLAM implementations had computational complexities ranging from O(Nlog(N)) to O(N²), where N is the number of map features. Unlike these methods, our approach reduces the computational complexity to O(N) by using a model to fuse the information from the sensors after applying the Bayesian paradigm. Once the training process is completed, the robot identifies and locates those areas that potentially match the sections that have been previously learned. After the training, the robot navigates and extracts a three-dimensional map of the environment using a single laser sensor. Thus, it perceives different sections of its world. In addition, in order to make our system able to be used in a low-cost robot, low-complexity algorithms that can be easily implemented on embedded processors or microcontrollers are used.     

Efficient maximum likelihood pedigree reconstruction

A simple and efficient algorithm is presented for finding a maximum likelihood pedigree using microsatellite (STR) genotype information on a complete sample of related individuals. The computational complexity of the algorithm is at worst (O(n³2ⁿ)), where n is the number of individuals. Thus it is possible to exhaustively search the space of all pedigrees of up to thirty individuals for one that maximizes the likelihood. A priori age and sex information can be used if available, but is not essential. The algorithm is applied in a simulation study, and to some real data on humans.     

A Simple Algorithm for Finding All k-Edge-Connected Components

The problem of finding k-edge-connected components is a fundamental problem in computer science. Given a graph G = (V, E), the problem is to partition the vertex set V into {V ₁, V ₂,…, V _h}, where each V _i is maximized, such that for any two vertices x and y in V _i, there are k edge-disjoint paths connecting them. In this paper, we present an algorithm to solve this problem for all k. The algorithm preprocesses the input graph to construct an Auxiliary Graph to store information concerning edge-connectivity among every vertex pair in O(Fn) time, where F is the time complexity to find the maximum flow between two vertices in graph G and n = ∣V∣. For any value of k, the k-edge-connected components can then be determined by traversing the auxiliary graph in O(n) time. The input graph can be a directed or undirected, simple graph or multigraph. Previous works on this problem mainly focus on fixed value of k.     

Thermodynamics of Long Supercoiled Molecules: Insights from Highly Efficient Monte Carlo Simulations

Supercoiled DNA polymer models for which the torsional energy depends on the total twist of molecules (Tw) are a priori well suited for thermodynamic analysis of long molecules. So far, nevertheless, the exact determination of Tw in these models has been based on a computation of the writhe of the molecules (Wr) by exploiting the conservation of the linking number, Lk = Tw + Wr, which reflects topological constraints coming from the helical nature of DNA. Because Wr is equal to the number of times the main axis of a DNA molecule winds around itself, current Monte Carlo algorithms have a quadratic time complexity, O(L²), with respect to the contour length (L) of the molecules. Here, we present an efficient method to compute Tw exactly, leading in principle to algorithms with a linear complexity, which in practice is O(L^1.2). Specifically, we use a discrete wormlike chain that includes the explicit double-helix structure of DNA and where the linking number is conserved by continuously preventing the generation of twist between any two consecutive cylinders of the discretized chain. As an application, we show that long (up to 21 kbp) linear molecules stretched by mechanical forces akin to magnetic tweezers contain, in the buckling regime, multiple and branched plectonemes that often coexist with curls and helices, and whose length and number are in good agreement with experiments. By attaching the ends of the molecules to a reservoir of twists with which these can exchange helix turns, we also show how to compute the torques in these models. As an example, we report values that are in good agreement with experiments and that concern the longest molecules that have been studied so far (16 kbp).     

Ordering process of self-organizing maps improved by asymmetric neighborhood function

The Self-organizing map (SOM) is an unsupervised learning method based on the neural computation, which has found wide applications. However, the learning process sometime takes multi-stable states, within which the map is trapped to an undesirable disordered state including topological defects on the map. These topological defects critically aggravate the performance of the SOM. In order to overcome this problem, we propose to introduce an asymmetric neighborhood function for the SOM algorithm. Compared with the conventional symmetric one, the asymmetric neighborhood function accelerates the ordering process even in the presence of the defect. However, this asymmetry tends to generate a distorted map. This can be suppressed by an improved method of the asymmetric neighborhood function. In the case of one-dimensional SOM, it is found that the required steps for perfect ordering is numerically shown to be reduced from O(N ³) to O(N ²). We also discuss the ordering process of a twisted state in two-dimensional SOM, which can not be rectified by the ordinary symmetric neighborhood function.     

Rapid Evaluation of Least-Squares and Minimum-Evolution Criteria on Phylogenetic Trees

We present fast new algorithms for evaluating trees with respectto least squares and minimum evolution (ME), the most commonlyused criteria for inferring phylogenetic trees from distancedata. The new algorithms include an optimal O(N2) time algorithmfor calculating the edge (branch or internode) lengths on atree according to ordinary or unweighted least squares (OLS);an O(N3) time algorithm for edge lengths under weighted leastsquares (WLS) including the Fitch-Margoliash method; and anoptimal O(N4) time algorithm for generalized least-squares (GLS)edge lengths (where N is the number of taxa in the tree). TheME criterion is based on the sum of edge lengths. Consequently,the edge lengths algorithms presented here lead directly toO(N2), O(N3), and O(N4) time algorithms for ME under OLS, WLS,and GLS, respectively. All of these algorithms are as fast asor faster than any of those previously published, and the algorithmsfor OLS and GLS are the fastest possible (with respect to orderof computational complexity). A major advantage of our new methodsis that they are as well adapted to multifurcating trees asthey are to binary trees. An optimal algorithm for determiningpath lengths from a tree with given edge lengths is also developed.This leads to an optimal O(N2) algorithm for OLS sums of squaresevaluation and corresponding O(N3) and O(N4) time algorithmsfor WLS and GLS sums of squares, respectively. The GLS algorithmis time-optimal if the covariance matrix is already inverted.The speed of each algorithm is assessed analytically—thespeed increases we calculate are confirmed by the dramatic speedincreases resulting from their implementation in PAUP* 4.0.The new algorithms enable far more extensive tree searches andstatistical evaluations (e.g., bootstrap, parametric bootstrap,or jackknife) in the same amount of time. Hopefully, the fastalgorithms for WLS and GLS will encourage the use of these criteriafor evaluating trees and their edge lengths (e.g., for approximatedivergence time estimates), since they should be more statisticallyefficient than OLS.     

PROuST: a comparison method of three-dimensional structures of proteins using indexing techniques.

We present a new method for protein structure comparison that combines indexing and dynamic programming (DP). The method is based on simple geometric features of triplets of secondary structures of proteins. These features provide indexes to a hash table that allows fast retrieval of similarity information for a query protein. After the query protein is matched with all proteins in the hash table producing a list of putative similarities, the dynamic programming algorithm is used to align the query protein with each protein of this list. Since the pairwise comparison with DP is applied only to a small subset of proteins and, furthermore, DP re-uses information that is already computed and stored in the hash table, the approach is very fast even when searching the entire PDB. We have done extensive experimentation showing that our approach achieves results of quality comparable to that of other existing approaches but is generally faster.     

Preconditioning 2D Integer Data for Fast Convex Hull Computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.     

O-benzylated thio sugars: 2,3,4- and 2,4,6-tri-O-benzyl-1-thio-β-d-galactopyranose

The 2,3,4- (9) and 2,4,6-tribenzyl (19) ethers of 1-thio-β-d-galactopyranose were prepared from the corresponding O-benzylated normal (1-hydroxyl) sugars 4 and 15 via the sequence: normal sugar → diacetate → O-acetylglycosyl bromide → O-acetyl-glycosyl ethylxanthate → 1-thio sugar. 2,3,4-Tri-O-benzyl-α-d-galactopyranose (4) is most advantageously made from allyl 6-O-allyl-α-d-galactopyranoside (2) by a published synthesis. An improved synthesis of 2,4,6-tri-O-benzyl-d-galactopyranose (15) was devised; it involves the selective 3-O-benzoylation of allyl 2,6-di-O-benzyl-α-d-galactopyranoside (10).     

Identification of a Novel Di-D-Fructofuranose 1,2’:2,3’ Dianhydride (DFA III) Hydrolysis Enzyme from Arthrobacter aurescens SK8.001

Previously, a di-D-fructofuranose 1,2’:2,3’ dianhydride (DFA III)-producing strain, Arthrobacter aurescens SK8.001, was isolated from soil, and the gene cloning and characterization of the DFA III-forming enzyme was studied. In this study, a DFA III hydrolysis enzyme (DFA IIIase)-encoding gene was obtained from the same strain, and the DFA IIIase gene was cloned and expressed in Escherichia coli. The SDS-PAGE and gel filtration results indicated that the purified enzyme was a homotrimer holoenzyme of 145 kDa composed of subunits of 49 kDa. The enzyme displayed the highest catalytic activity for DFA III at pH 5.5 and 55°C, with specific activity of 232 U mg^-1. K _m and V _max for DFA III were 30.7 ± 4.3 mM and 1.2 ± 0.1 mM min^-1, respectively. Interestingly, DFA III-forming enzymes and DFA IIIases are highly homologous in amino acid sequence. The molecular modeling and docking of DFA IIIase were first studied, using DFA III-forming enzyme from Bacillus sp. snu-7 as a template. It was suggested that A. aurescens DFA IIIase shared a similar three-dimensional structure with the reported DFA III-forming enzyme from Bacillus sp. snu-7. Furthermore, their catalytic sites may occupy the same position on the proteins. Based on molecular docking analysis and site-directed mutagenesis, it was shown that D207 and E218 were two potential critical residues for the catalysis of A. aurescens DFA IIIase.     

A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation

The minimum spanning tree (MST) problem is to find minimum edge connected subsets containing all the vertex of a given undirected graph. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications. Moreover in previous studies, DNA molecular operations usually were used to solve NP-complete head-to-tail path search problems, rarely for NP-hard problems with multi-lateral path solutions result, such as the minimum spanning tree problem. In this paper, we present a new fast DNA algorithm for solving the MST problem using DNA molecular operations. For an undirected graph with n vertex and m edges, we reasonably design flexible length DNA strands representing the vertex and edges, take appropriate steps and get the solutions of the MST problem in proper length range and O(3m + n) time complexity. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation. Results of computer simulative experiments show that the proposed method updates some of the best known values with very short time and that the proposed method provides a better performance with solution accuracy over existing algorithms.     

The synthesis of 5-O-(2-acetamido-2-deoxy-α-D-glucopyranosyl)-β-D-glucofuranose

Condensation of dimeric 3,4,6-tri-O-acetyl-2-deoxy-2-nitroso-α-D-glucopyranosyl chloride (1) with 1,2-O-isopropylidene-α-D-glucofuranurono-6,3-lactone (2) gave 1,2-O-isopropylidene-5-O-(3,4,6-tri-O-acetyl-2-deoxy-2-hydroxyimino-α-D-arabino-hexopyranosyl)-α-D-glucofuranurono-6,3-lactone (3). Benzoylation of the hydroxyimino group with benzoyl cyanide in acetonitrile gave 1,2-O-isopropylidene-5-O-(3,4,6-tri-O-acetyl-2-benzoyloxyimino-2-deoxy-α-D-arabino-hexopyranosyl)-α-D-glucofuranurono-6,3-lactone (4). Compound 4 was reduced with borane in tetrahydrofuran, yielding 5-O-(2-amino-2-deoxy-α-D-glucopyranosyl)-1,2-O-isopropylidene-α-D-glucofuranose (5), which was isolated as the crystalline N-acetyl derivative (6). After removal of the isopropylidene acetal, the pure, crystalline title compound (10) was obtained.     

Modeling of the three-dimensional structure of luffin-α and its simulated reaction with the substrate oligoribonucleotide GAGA

A fundamental problem in biochemistry and molecular biology is understanding the spatial structure of macromolecules and then analyzing their functions. In this study, the three-dimensional structure of a ribosome-inactivating protein luffin-α was predicted using a neural network method and molecular dynamics simulation. A feedforward neural network with the backpropagation learning algorithm were trained on model class of homologous proteins including trichosanthin andα-momorcharin. The distance constraints for the Cα atoms in the protein backbone were utilized to generate a folded crude conformation of luffin-α by model building and the steepest descent minimization approach. The crude conformation was refined by molecular dynamics techniques and a simulated annealing procedure. The interaction between luffin-α and its analogous substrate GAGA was also simulated to understand its action mechanism.     

Synthesis of benzyl and allyl ethers of D-glucopyranose

Starting from allyl 3-O-benzyl-4,6-O-benzylidene-α-D-glucopyranoside as a key intermediate, the following crystalline compounds were prepared: 2-O-allyl-3,4,6-tri-O-benzyl-D-glucopyranose (11) and its p-nitrobenzoate; 2,3,5-tri-O-benzyl-D-arabinofuranose (12) and the corresponding arabinitol; allyl 3,4,6-tri-O-benzyl-α-D-glucopyranoside (7); 3,4,6-tri-O-benzyl-D-glucopyranose (8); 2-O-allyl-3,4-di-O-benzyl-D-glucopyranose (17) and its bis(p-nitrobenzoate); and 3,4-di-O-benzyl-D-glucopyranose (19). The p-nitrobenzoates of compounds 11 and 17 are potential intermediates for the synthesis of the glycolipids of the cytoplasmic membranes of Streptococci.     

Derivatives of 2,5-anhydroallitol and 2,5-anhydroaltritol

Two routes to protected derivatives of 2,5-anhydroallitol were investigated. The first route, involving a two-step reduction of 2,5-anhydro-6-O-benzoyl-3,4-O-isopropylidene-D-allonitrile (4), gave a mixture of 2,5-anhydro-6-O-benzoyl-3,4-O-isopropylidene-D-altritol (7) and a lesser amount of the desired 2,5-anhydro-6-O-benzoyl-3,4-O-isopropylidene-D-allitol (6). Isomerization was shown to occur in the first reduction step—treatment of the nitrile 4 with Raney nickel, sodium hypophosphite, and acetic acid. The second route gave isomerically pure 2,5-anhydro-3,4,6-tri-O-benzyl-D-allitol (21) via reduction of the corresponding ethyl allonate (18).     

5-thio-l-rhamnose

Two routes for the synthesis of methyl 5-S-acetyl-6-deoxy-2,3-O-isopropylidene-5-thio-l-mannofuranoside (8) have been examined. Reaction of l-rhamnose with methanol in the presence of the cation-exchange resin gives methyl 6-deoxy-α-l-mannofuranoside (2), which on conventional acetonation yields methyl 6-deoxy-2,3-O- isopropylidene-α-l-mannofuranosides (3). Compounds 3 is also obtained by acetonation of l-rhamnose followed by treatment with a mixture of methanol, acetonation, Amberlite IR-120(H⁺) resin. Chlorination of 3 with triphenylphosphine-carbon tetrachloride gives methyl 5-chloro-5,6-dideoxy-2,3-O-isopropylidene-β-d-gulofuranoside (7), which reacts with potassium thioacetate to give 8. Alternatively, 3 is iodized with ruthenium tetraoxide to methyl 6-deoxy-2,3-O-isopropylidene-α-l-lyxo-hexofuranosid-5-ulose (9), which reduced by sodium borohydride mainly to methyl 6-deoxy-2,3-O-isopropylidene-β-d-gulofuranoside (10). The O-tosyl derivative of 10 reacts with potassium thioacetate to produced 8. Hydrolysis of 8 with 90% aqueous triflouroacetic acid, followed by acetolysis with a solution of acetic acid, acetic anhydride, and sulfuric acids gives an anomeric mixture of 1,2,3,4,-tetra-O-acetyl-6-deoxy-5-thio-l-mannopyranoses (12), together with a small proportion of 1,2,3,-tri-O-acetyl-5-S-acetyl-6-deoxy-5-thio-β-l-mannofuranose (13). Deacetylation of 12 or 13 gives 5-thio-l-rhamnose (6), from which crystalline 1,2,3,4-tetra-O-(p-nitrobenzoyl)-5-thio-β-l-rhamnopyranose (14) is obtained.