An ILP solution for the gene duplication problem

Background

The gene duplication (GD) problem seeks a species tree that implies the fewest gene duplication events across a given collection of gene trees. Solving this problem makes it possible to use large gene families with complex histories of duplication and loss to infer phylogenetic trees. However, the GD problem is NP-hard, and therefore, most analyses use heuristics that lack any performance guarantee.

Results

We describe the first integer linear programming (ILP) formulation to solve instances of the gene duplication problem exactly. With simulations, we demonstrate that the ILP solution can solve problem instances with up to 14 taxa. Furthermore, we apply the new ILP solution to solve the gene duplication problem for the seed plant phylogeny using a 12-taxon, 6, 084-gene data set. The unique, optimal solution, which places Gnetales sister to the conifers, represents a new, large-scale genomic perspective on one of the most puzzling questions in plant systematics.

Conclusions

Although the GD problem is NP-hard, our novel ILP solution for it can solve instances with data sets consisting of as many as 14 taxa and 1, 000 genes in a few hours. These are the largest instances that have been solved to optimally to date. Thus, this work can provide large-scale genomic perspectives on phylogenetic questions that previously could only be addressed by heuristic estimates.

     

Genome duplication, divergent resolution and speciation

What are the evolutionary consequences of gene duplication? One answer is speciation, according to a model initially called Reciprocal Silencing and recently expanded and renamed Divergent Resolution. This model shows how the loss of different copies of a duplicated gene in allopatric populations (divergent resolution) can promote speciation by genetically isolating these populations should they become reunited. Genome duplication events produce thousands of duplicated genes. Therefore, lineages with a history of genome duplication might have been especially prone to speciation via divergent resolution.     

A model for the minimum cost configuration problem in flexible manufacturing systems

This paper presents a mathematical programming model to help select equipment for a flexible manufacturing system, i.e., the selection of the types and numbers of CNC machines, washing stations, load/unload stations, transportation vehicles, and pallets. The objective is to minimize equipment costs and work-in-process inventory cost, while fulfilling production requirements for an average period. Queueing aspects and part flow interactions are considered with the help of a Jacksonian-type closed queueing network model in order to evaluate the system's performance. Since the related decision problem of our model can be shown to be NP-complete, the proposed solution procedure is based on implicit enumeration. Four bounds are provided, two lower and two upper bounds. A tight lower bound is obtained by linearizing the model through the application of asymptotic bound analysis. Furthermore, asymptotic bound analysis allows the calculation of a lower bound for the number of pallets in the system. The first upper bound is given by the best feasible solution and the second is based on the anti-starshaped form of the throughput function.     

A 1.375-approximation algorithm for sorting by transpositions

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: We improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations     

The multiple gene duplication problem revisited

MOTIVATION: Deciphering the location of gene duplications and multiple gene duplication episodes on the Tree of Life is fundamental to understanding the way gene families and genomes evolve. The multiple gene duplication problem provides a framework for placing gene duplication events onto nodes of a given species tree, and detecting episodes of multiple gene duplication. One version of the multiple gene duplication problem was defined by Guigó et al. in 1996. Several heuristic solutions have since been proposed for this problem, but no exact algorithms were known. RESULTS: In this article we solve this longstanding open problem by providing the first exact and efficient solution. We also demonstrate the improvement offered by our algorithm over the best heuristic approaches, by applying it to several simulated as well as empirical datasets.     

Parallel deterministic local search heuristic for minimum latency problem

Cluster Computing - Minimum latency problem (MLP) is an NP-Hard combinatorial optimization problem. Metaheuristics use perturbation and randomization to arrive at a satisfactory solution under time...     

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.     

A (1.5 + epsilon)-approximation algorithm for unsigned translocation distance

Genome rearrangement is an important area in computational biology and bioinformatics. The translocation operation is one of the popular operations for genome rearrangement. It was proved that computing the unsigned translocation distance is NP-hard. In this paper, we present a (1.5 + epsilon)-approximation algorithm for computing unsigned translocation distance which improves upon the best known 1.75-ratio. The running time of our algorithm is O(n2 + (4/epsilon)1.5 square root log(4/epsilon )2(4/epsilon), where n is the total number of genes in the genome.     

A general correlation for the minimum spouting velocity

In this paper new correlations are developed, for cases where the height of the bed to column diameter ratio (H/D _c ) is below and above unity. Based on 356 published data points (16 different sources with 23 different solids with a wide range of variables) along with those of the author are used for developing the correlations. The present proposed equations are more exact and simpler to use than previous empirical correlation.     

Significantly different patterns of amino acid replacement after gene duplication as compared to after speciation

We have performed a large-scale analysis of amino acid sequence evolution after gene duplication by comparing evolution after gene duplication with evolution after speciation in over 1,800 phylogenetic trees constructed from manually curated alignments of protein domains downloaded from the PFAM database. The site-specific rate of evolution is significantly altered by gene duplication. A significant increase in the proportion of amino acid substitutions at constrained (slowly evolving) sites after duplication was observed. An increase in the proportion of replacements at normally constrained amino acid sites could result from relaxation of purifying selective pressure. However, the proportion of amino acid replacements involving radical changes in amino acid properties after duplication does not appear to be significantly increased by relaxed selective pressure. The increased proportion of replacements at constrained sites was observed over a relatively large range of protein change (up to 25% amino acid replacements per site). These findings have implications for our understanding of the nature of evolution after duplication and may help to shed light on the evolution of novel protein functions through gene duplication.     

A distance-based least-square method for dating speciation events

Distance-based phylogenetic methods are widely used in biomedical research. However, there has been little development of rigorous statistical methods and software for dating speciation and gene duplication events by using evolutionary distances. Here we present a simple, fast and accurate dating method based on the least-squares (LS) method that has already been widely used in molecular phylogenetic reconstruction. Dating methods with a global clock or two different local clocks are presented. Single or multiple fossil calibration points can be used, and multiple data sets can be integrated in a combined analysis. Variation of the estimated divergence time is estimated by resampling methods such as bootstrapping or jackknifing. Application of the method to dating the divergence time among seven ape species or among 35 mammalian species including major mammalian orders shows that the estimated divergence time with the LS criterion is nearly identical to those obtained by the likelihood method or Bayesian inference.     

A stepwise algorithm for finding minimum evolution trees

A stepwise algorithm for reconstructing minimum evolution (ME) trees from evolutionary distance data is proposed. In each step, a taxon that potentially has a neighbor (another taxon connected to it with a single interior node) is first chosen and then its true neighbor searched iteratively. For m taxa, at most (m-1)!/2 trees are examined and the tree with the minimum sum of branch lengths (S) is chosen as the final tree. This algorithm provides simple strategies for restricting the tree space searched and allows us to implement efficient ways of dynamically computing the ordinary least squares estimates of S for the topologies examined. Using computer simulation, we found that the efficiency of the ME method in recovering the correct tree is similar to that of the neighbor-joining method (Saitou and Nei 1987). A more exhaustive search is unlikely to improve the efficiency of the ME method in finding the correct tree because the correct tree is almost always included in the tree space searched with this stepwise algorithm. The new algorithm finds trees for which S values may not be significantly different from that of the ME tree if the correct tree contains very small interior branches or if the pairwise distance estimates have large sampling errors. These topologies form a set of plausible alternatives to the ME tree and can be compared with each other using statistical tests based on the minimum evolution principle. The new algorithm makes it possible to use the ME method for large data sets.      

A mammalian in vitro centriole duplication system: evidence for involvement of CDK2/cyclin E and nucleophosmin/B23 in centrosome duplication

Centrosome duplication in mammalian cells is a highly regulated process, occurs in coordination of other cell cycle events. However, molecular exploration of this important cellular process had been difficult due to unavailability of a simple assay system. Here, using centrosomes loosely associated with nuclei isolated from cultured cells, we developed a cell-free centriole (duplication unit of the centrosome) duplication system: unduplicated centrosomes bound to the nuclei are able to undergo duplication in the presence of G1/S extracts. We show that the ability of G1/S extracts to induce centriole duplication in vitro depends on the presence of active CDK2/cyclin E. It has been shown that dissociation of centro-somal nucleophosmin (NPM)/B23 triggered by CDK2/cyclin E-mediated phosphorylation is required for initiation of centrosome duplication. We show that centriole duplication is blocked when nuclei were preincubated with the anti-NPM/B23 antibody that prevents phosphorylation of NPM/B23 by CDK2/cyclin E. These studies provide not only direct evidence for the requirement of CDK2/cyclin E and phosphorylation of NPM/B23 for centrosomes to initiate duplication, but a valuable experimental system for further exploration of the molecular regulation of centrosome duplication in somatic cells of higher animals.     

Mosaicism for the Charcot-Marie-Tooth disease type 1A duplication suggests somatic reversion

A female patient with clinical signs and symptoms of a demyelinating neuropathy was shown to have a duplication of the 1.5-Mb region on chromosome 17p11.2, typical of the great majority of cases of Charcot-Marie-Tooth disease type 1A (CMT1A). However, analysis of DNA extracted from peripheral blood revealed a 2:2.4 instead of the usual 2:3 ratio between the 7.8- and 6.0-kb EcoRI fragments in the proximal and distal repetitive extragenic palindromic (REP) elements of CMT1A. Detection of a 3.2-kb EcoRI/SacI kb junction fragment with probe pLR7.8 confirmed the CMT1A duplication. The dosage of this junction fragment, compared with a 2.8-kb EcoRI/SacI fragment of the proximal REP elements of CMT1A, was 2:0.58 instead of the expected 2:1 dosage for heterozygous CMT1A duplications. We hypothesized that the lower dosages of these restriction fragments specific for the CMT1A duplication were due to mosaicism; this was confirmed by fluorescence in situ hybridization analysis with the D17S122-specific probe pVAW409R1. In peripheral blood lymphocytes the percentage of interphase nuclei with a duplication in 17p11.2 was 49%. In interphase nuclei extracted from buccal mucosa, hair-root cells or paraffin-embedded nervous tissue the duplication was detectable in 51%, 66% and 74%, respectively. This is the first report of mosaicism in a patient with a CMT1A duplication identified by three different and independent techniques. Received: 14 November 1995 / Revised: 13 February 1996