Two New PRP Conjugate Gradient Algorithms for Minimization Optimization Models

Two new PRP conjugate Algorithms are proposed in this paper based on two modified PRP conjugate gradient methods: the first algorithm is proposed for solving unconstrained optimization problems, and the second algorithm is proposed for solving nonlinear equations. The first method contains two aspects of information: function value and gradient value. The two methods both possess some good properties, as follows: 1)β _k ≥ 0 2) the search direction has the trust region property without the use of any line search method 3) the search direction has sufficient descent property without the use of any line search method. Under some suitable conditions, we establish the global convergence of the two algorithms. We conduct numerical experiments to evaluate our algorithms. The numerical results indicate that the first algorithm is effective and competitive for solving unconstrained optimization problems and that the second algorithm is effective for solving large-scale nonlinear equations.     

Fast local fragment chaining using sum-of-pair gap costs

Background

When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees.

Results

We have derived a new algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degree ≥ 3. The time and space complexity of our algorithm is sub-cubic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm so far for computing the quartet distance between general trees independent of the degree of the inner nodes.

Conclusions

We have implemented our algorithm and two of the best competitors. Our new algorithm is significantly faster than the competition and seems to run in close to quadratic time in practice.     

A new distance for high level RNA secondary structure comparison

We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations of deletion, insertion, and relabeling classically used in the literature. This allows us to address some serious limitations of the more traditional tree edit operations when the trees represent RNAs and what is searched for is a common structural core of two RNAs. Although the algorithm complexity has an exponential term, this term depends only on the number of successive fusions that may be applied to a same node, not on the total number of fusions. The algorithm remains therefore efficient in practice and is used for illustrative purposes on ribosomal as well as on other types of RNAs.     

Improved algorithms for finding gene teams and constructing gene team trees

A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold δ. A gene team tree is a succinct way to represent all gene teams for every possible value of δ. In this paper, improved algorithms are presented for the problem of finding the gene teams of two chromosomes and the problem of constructing a gene team tree of two chromosomes. For the problem of finding gene teams, Beal et al. had an O(n lg2 n)-time algorithm. Our improved algorithm requires O(n lg t) time, where t ≤ n is the number of gene teams. For the problem of constructing a gene team tree, Zhang and Leong had an O(n lg2 n)-time algorithm. Our improved algorithm requires O(n lg n lglg n) time. Similar to Beal et al.'s gene team algorithm and Zhang and Leong's gene team tree algorithm, our improved algorithms can be extended to k chromosomes with the time complexities increased only by a factor of k.     

Network algorithm for the Exact Test of Hardy‐Weinberg Proportion for Multiple Alleles

We propose a new technique for the exact test of Hardy‐Weinberg proportion that considerably extends the bounds of computational feasibility. Our algorithm is constructed analogously to the network algorithm for Freeman‐Halton exact test in two‐way contingency tables. In this algorithm, the smallest and the largest values for the statistic are important and some interesting new theorems are proved for computing these values. Numerical examples are given to illustrate the practicality of our algorithm.     

COMPUTER PROGRAMS: d-novl: a program to simulate overlap between two niche-based distribution models

d-novl is a Monte Carlo program designed to generate a null expectation of overlap between two niche-based distribution models. The user may choose between two growth algorithms: the separated algorithm grows a random number of disjointed growth areas, whereas the number of islands algorithm allows the user to input the desired number of growth areas. The latter algorithm can also be used to grow a single growth area. The resulting probability distribution of expected overlap values can be exported into a spreadsheet for further analysis. d-novl is freely available for Mac and Windows platforms at http://www.mygalomorphae.org.     

Spaceborne SAR Imaging Algorithm for Coherence Optimized

This paper proposes SAR imaging algorithm with largest coherence based on the existing SAR imaging algorithm. The basic idea of SAR imaging algorithm in imaging processing is that output signal can have maximum signal-to-noise ratio (SNR) by using the optimal imaging parameters. Traditional imaging algorithm can acquire the best focusing effect, but would bring the decoherence phenomenon in subsequent interference process. Algorithm proposed in this paper is that SAR echo adopts consistent imaging parameters in focusing processing. Although the SNR of the output signal is reduced slightly, their coherence is ensured greatly, and finally the interferogram with high quality is obtained. In this paper, two scenes of Envisat ASAR data in Zhangbei are employed to conduct experiment for this algorithm. Compared with the interferogram from the traditional algorithm, the results show that this algorithm is more suitable for SAR interferometry (InSAR) research and application.     

Inference of biological S-system using the separable estimation method and the genetic algorithm

Reconstruction of a biological system from its experimental time series data is a challenging task in systems biology. The S-system which consists of a group of nonlinear ordinary differential equations (ODEs) is an effective model to characterize molecular biological systems and analyze the system dynamics. However, inference of S-systems without the knowledge of system structure is not a trivial task due to its nonlinearity and complexity. In this paper, a pruning separable parameter estimation algorithm (PSPEA) is proposed for inferring S-systems. This novel algorithm combines the separable parameter estimation method (SPEM) and a pruning strategy, which includes adding an l? regularization term to the objective function and pruning the solution with a threshold value. Then, this algorithm is combined with the continuous genetic algorithm (CGA) to form a hybrid algorithm that owns the properties of these two combined algorithms. The performance of the pruning strategy in the proposed algorithm is evaluated from two aspects: the parameter estimation error and structure identification accuracy. The results show that the proposed algorithm with the pruning strategy has much lower estimation error and much higher identification accuracy than the existing method.     

A novel approach to the detection of genomic approximate tandem repeats in the Levenshtein metric.

An efficient algorithm for detecting approximate tandem repeats in genomic sequences is presented. The algorithm is based on innovative statistical criteria to detect candidate regions which may include tandem repeats; these regions are subsequently verified by alignments based on dynamic programming. No prior information about the period size or pattern is needed. Also, the algorithm is virtually capable of detecting repeats with any period. An implementation of the algorithm is compared with the two state-of-the-art tandem repeats detection tools to demonstrate its effectiveness both on natural and synthetic data. The algorithm is available at www.cs.brown.edu/people/domanic/tandem/.     

Simultaneous search for multiple QTL using the global optimization algorithm DIRECT

MOTIVATION: A simultaneous search is necessary for maximizing the power to detect epistatic quantitative trait loci (QTL). The computational complexity demands that the traditional exhaustive search be replaced by a more efficient global optimization algorithm. RESULTS: We have the previously known algorithm adapted DIRECT, to the problem of simultaneous mapping of multiple QTL. We have compared DIRECT with standard exhaustive search and a genetic algorithm previously used for QTL mapping in two dimensions. In all two- and three-QTL test cases, DIRECT accurately finds the global optimum two to four orders of magnitude faster than when using an exhaustive search, and one order of magnitude faster than when using the genetic algorithm. Thus, randomization testing for determining empirical significance thresholds for at least three QTL is made feasible by the use of DIRECT. AVAILABILITY: The code of the prototype implementation is available at http://user.it.uu.se/~kl/qtl_software.html     

SARS病毒再测序DNA微阵列的探针设计

探针设计是SARS病毒再测序DNA微阵列制作的关键步骤,为了保证探针的杂交条件尽可能一致,采用了作者提出的两种等长变覆盖的探针设计方法,即基于Tm距离的算法和遗传算法。针对SAILS病毒基因组中的两段特异序列设计了一组探针,并与等长移位法和变长变覆盖法的设计结果进行了比较。等长变覆盖法得到的探针集在探针长度一致的情况下,探针的Tm值有较小的标准差和变化范围。结果表明,等长变覆盖法得到的探针具有更好的杂交条件一致性。     

A three-dimensional model of the human airway tree.

A three-dimensional (3D) model of the human airway tree is proposed using a deterministic algorithm that can generate a branching duct system in an organ. The algorithm is based on two principles: 1) the amount of fluid delivery through a branch is proportional to the volume of the region it supplies; and 2) the terminal branches are arranged homogeneously within the organ. These principles define the basic process of branching: generation of the dimensions and directionality of two daughter branches is governed by the properties of the parent branch and the region the parent supplies. The algorithm is composed of nine basic rules and four complementary rules. When the contour of an organ and the position of the trunk are specified, branches are successively generated by the algorithm. Applied to the human lung, the algorithm generates an airway tree that consists of approximately 54,000 branches. Its morphometric characteristics are in good agreement with those reported in the literature. The algorithm and the 3D airway model are useful for studying the structure-function relationship in the lung.     

A linear-time algorithm for computing inversion distance between signed permutations with an experimental study.

Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, as part of the larger task of determining the shortest sequence of inversions needed to transform one permutation into the other. Their algorithm (restricted to distance calculation) proceeds in two stages: in the first stage, the overlap graph induced by the permutation is decomposed into connected components; then, in the second stage, certain graph structures (hurdles and others) are identified. Berman and Hannenhalli avoided the explicit computation of the overlap graph and gave an O(nalpha(n)) algorithm, based on a Union-Find structure, to find its connected components, where alpha is the inverse Ackerman function. Since for all practical purposes alpha(n) is a constant no larger than four, this algorithm has been the fastest practical algorithm to date. In this paper, we present a new linear-time algorithm for computing the connected components, which is more efficient than that of Berman and Hannenhalli in both theory and practice. Our algorithm uses only a stack and is very easy to implement. We give the results of computational experiments over a large range of permutation pairs produced through simulated evolution; our experiments show a speed-up by a factor of 2 to 5 in the computation of the connected components and by a factor of 1.3 to 2 in the overall distance computation.     

Computerized tomography using a modified orthogonal tangent correction algorithm.

A modified orthogonal tangent correction algorithm is presented for computerized tomography. The algorithm uses four X-rays scans spaced 45 degrees apart, to reconstruct a transverse axial image. The reconstruction procedure is interative in which image matrix elements are corrected by alternately matching the two sets of orthogonal scan data. The algorithm has been applied to phantom data as well as to video recorded fluoroscopic data.     

Protein structure comparison using bipartite graph matching and its application to protein structure classification

A measure of protein structure similarity is calculated from the matching of pairs of secondary structure elements between two proteins. The interaction of each pair was estimated from their axial line segments and combined with other geometric features to produce an optimal discrimination between intrafamily and interfamily relationships. The matching used a fast bipartite graph-matching algorithm that avoids the computational complexity of searching for the full subgraph isomorphism between the two sets of interactions. The main algorithm used was the "stable marriage" algorithm, which works on the ranked "preferences" of one interaction for another. The method takes 1/10 of a second for a typical comparison making it suitable as a fast pre-filter for slower, more exhaustive approaches. An application to protein structure classification is described.     

Unbiased estimation of evolutionary distance between nucleotide sequences

A new algorithm for estimating the number of nucleotide substitutions per site (i.e., the evolutionary distance) between two nucleotide sequences is presented. This algorithm can be applied to many estimation methods, such as Jukes and Cantor's method, Kimura's transition/transversion method, and Tajima and Nei's method. Unlike ordinary methods, this algorithm is always applicable. Numerical computations and computer simulations indicate that this algorithm gives an almost unbiased estimate of the evolutionary distance, unless the evolutionary distance is very large. This algorithm should be useful especially when we analyze short nucleotide sequences. It can also be applied to amino acid sequences, for estimating the number of amino acid replacements.      

A Fast Image Alignment Approach for 2D Classification of Cryo-EM Images Using Spectral Clustering

Three-dimensional (3D) reconstruction in single-particle cryo-electron microscopy (cryo-EM) is a significant technique for recovering the 3D structure of proteins or other biological macromolecules from their two-dimensional (2D) noisy projection images taken from unknown random directions. Class averaging in single-particle cryo-EM is an important procedure for producing high-quality initial 3D structures, where image alignment is a fundamental step. In this paper, an efficient image alignment algorithm using 2D interpolation in the frequency domain of images is proposed to improve the estimation accuracy of alignment parameters of rotation angles and translational shifts between the two projection images, which can obtain subpixel and subangle accuracy. The proposed algorithm firstly uses the Fourier transform of two projection images to calculate a discrete cross-correlation matrix and then performs the 2D interpolation around the maximum value in the cross-correlation matrix. The alignment parameters are directly determined according to the position of the maximum value in the cross-correlation matrix after interpolation. Furthermore, the proposed image alignment algorithm and a spectral clustering algorithm are used to compute class averages for single-particle 3D reconstruction. The proposed image alignment algorithm is firstly tested on a Lena image and two cryo-EM datasets. Results show that the proposed image alignment algorithm can estimate the alignment parameters accurately and efficiently. The proposed method is also used to reconstruct preliminary 3D structures from a simulated cryo-EM dataset and a real cryo-EM dataset and to compare them with RELION. Experimental results show that the proposed method can obtain more high-quality class averages than RELION and can obtain higher reconstruction resolution than RELION even without iteration.     

An efficient algorithm to locate all locally optimal alignments between two sequences allowing for gaps

An efficient algorithm is described to locate locally optimalalignments between two sequences allowing for insertions anddeletions. The algorithm is based on that of Smith and Watermanwhich returns the single best local alignment. However, thealgorithm described here permits all non-intersecting locallyoptimal alignments to be determined in a single pass throughthe comparison matrit The algorithm simplifies the locationof repeats, multiple domains and shuffled moz and is fast enoughto be used on a conventional workstation to scan large sequencedatabanks.     

Pairwise protein structure alignment based on an orientation-independent backbone representation

Determining structural similarities between proteins is an important problem since it can help identify functional and evolutionary relationships. In this paper, an algorithm is proposed to align two protein structures. Given the protein backbones, the algorithm finds a rigid motion of one backbone onto the other such that large substructures are matched. The algorithm uses a representation of the backbones that is independent of their relative orientations in space and applies dynamic programming to this representation to compute an initial alignment, which is then refined iteratively. Experiments indicate that the algorithm is competitive with two well-known algorithms, namely DALI and LOCK.