http://www.almob.org The latest research articles published by Algorithms for Molecular Biology 2010-02-03T00:00:00Z This is an RSS newsfeed from BioMed Central It is intended to be used with an RSS reader. For more information about RSS newsfeeds from BioMed Central, visit http://www.biomedcentral.com/info/about/rss/ Background: This paper describes the theory and implementation of a new software tool for the study ofhistorical associations. This problem arises in parasitology (associations of hosts and parasites), molecularsystematics (associations of organisms and genes), and biogeography (associations of regions and organisms).The underlying problem is that of reconciling pairs of trees subject to biologically plausible events and costsassociated with these events. Existing software tools for this problem have strengths and limitations, and theJane new tool described here provides functionality that complements existing tools. Results: The Jane software tool uses a polynomial time dynamic programming algorithm in conjunction with agenetic algorithm to find very good, and often optimal, solutions even for relatively large pairs of trees. The toolallows the user to provide rich timing information on both the host and parasite trees. In addition the user canlimit host switch distance and specify multiple host switch costs by specifying regions in the host tree and costsfor host switches between pairs of regions. Jane also provides a graphical user interface that allows the user tointeractively experiment with modifications to the solutions found by the program. Conclusions: The Jane tool is shown to be a useful tool for cophylogenetic reconstruction. Its functionalitycomplements existing tools and it is therefore likely to be of use to researchers in the areas of parasitology,molecular systematics, and biogeography. http://www.almob.org/content/5/1/16 Chris Conow Daniel Fielder Yaniv Ovadia Ran Libeskind-Hadas Algorithms for Molecular Biology 2010, 5:16 2010-02-03T00:00:00Z doi:10.1186/1748-7188-5-16 Algorithms for Molecular Biology 1748-7188 5 16 2010-02-03T00:00:00Z PDF Background: In bioinformatics it is common to search for a pattern of interest in a potentially large set of rather short sequences (upstream gene regions, proteins, exons, etc.). Although many methodological approaches allow practitioners to compute the distribution of a pattern count in a random sequence generated by a Markov source, no specific developments have taken into account the counting of occurrences in a set of independent sequences. We aim to address this problem by deriving efficient approaches and algorithms to perform these computations both for low and high complexity patterns in the framework of homogeneous or heterogeneous Markov models. Results: The latest advances in the field allowed us to use a technique of optimal Markov chain embedding based on deterministic finite automata to introduce three innovative algorithms. Algorithm 1 is the only one able to deal with heterogeneous models. It also permits to avoid any product of convolution of the pattern distribution in individual sequences. When working with homogeneous models, Algorithm 2 yields a dramatic reduction in the complexity by taking advantage of previous computations to obtain moment generating functions efficiently. In the particular case of low or moderate complexity patterns, Algorithm 3 exploits power computation and binary decomposition to further reduce the time complexity to a logarithmic scale. All these algorithms and their relative interest in comparison with existing ones were then tested and discussed on a toy-example and three biological data sets: structural patterns in protein loop structures, PROSITE signatures in a bacterial proteome, and transcription factors in upstream gene regions. On these data sets, we also compared our exact approaches to the tempting approximation that consists in concatenating the sequences in the data set into a single sequence. Conclusions: Our algorithms prove to be effective and able to handle real data sets with multiple sequences, as well as biological patterns of interest, even when the latter display a high complexity (PROSITE signatures for example). In addition, these exact algorithms allow us to avoid the edge effect observed under the single sequence approximation, which leads to erroneous results, especially when the marginal distribution of the model displays a slow convergence toward the stationary distribution. We end up with a discussion on our method and on its potential improvements. http://www.almob.org/content/5/1/15 Gregory Nuel Leslie Regad Juliette Martin Anne-Claude Camproux Algorithms for Molecular Biology 2010, 5:15 2010-01-26T00:00:00Z doi:10.1186/1748-7188-5-15 Algorithms for Molecular Biology 1748-7188 5 15 2010-01-26T00:00:00Z PDF Background: Accurate classification of microarray data is critical for successful clinical diagnosis and treatment.However, the "curse of dimensionality" problem, and noise in the data undermines the performance of many algorithms.MethodIn order to obtain a robust classifier, a novel Additive Nonparametric Margin Maximum for Case-Based Reasoning (ANMM4CBR) method is proposed in this article. ANMM4CBR employs a case-based reasoning (CBR) method for classification. CBR is a suitable paradigm for microarray analysis, where the rules that definethe domain knowledge are difficult to obtain since usually only a small number of training samples are available. Moreover, in order to select the most informative genes, we propose to perform feature selection via additively optimizing a nonparametric margin maximum criterion, which is defined based on gene pre-selection and sample clustering. Our feature selection method is very robust to noise in the data. Results: The effectiveness of our method is demonstrated on both simulated and real data sets. We show that the ANMM4CBR method performs better than some state-of-the-art methods such as support vector machine (SVM) and k nearest neighbor (kNN), especially when the data contains a great number of noise.AvailabilityThe source code is attached as an additional file of this paper. http://www.almob.org/content/5/1/14 Bangpeng Yao Shao Li Algorithms for Molecular Biology 2010, 5:14 2010-01-06T00:00:00Z doi:10.1186/1748-7188-5-14 Algorithms for Molecular Biology 1748-7188 5 14 2010-01-06T00:00:00Z PDF Background: The problem of computationally predicting the secondary structure (or folding) of RNA molecules was first introduced more than thirty years ago and yet continues to be an area of active research and development. The basic RNA-folding problem of finding a maximum cardinality, non-crossing, matching of complimentary nucleotides in an RNA sequence of length n, has an O(n^3)-time dynamic programming solution that is widely applied. It is known that an o(n^3) worst-case time solution is possible, but the published and suggested methods are complex and have not been established to be practical. Significant practical improvements to the original dynamic programming method have been introduced, but they retain the O(n^3) worst-case time bound when n is the only problem-parameter used in the bound. Surprisingly, the most widely-used, general technique to achieve a worst-case (and often practical) speed up of dynamic programming, the Four-Russians technique, has not been previously applied to the RNA-folding problem. This is perhaps due to technical issues in adapting the technique to RNA-folding. Results: In this paper, we give a simple, complete, and practical Four-Russians algorithm for the basic RNA-folding problem, achieving a worst-case time-bound of O(n^3/ log(n)). Conclusions: We show that this time-bound can also be obtained for richer nucleotide matching scoring-schemes, and that the method achieves consistent speed-ups in practice. The contribution is both theoretical and practical, since the basic RNA-folding problem is often solved multiple times in the inner-loop of more complex algorithms, and for long RNA molecules in the study of RNA virus genomes. http://www.almob.org/content/5/1/13 Yelena Frid Dan Gusfield Algorithms for Molecular Biology 2010, 5:13 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-13 Algorithms for Molecular Biology 1748-7188 5 13 2010-01-04T00:00:00Z PDF Background: Proteins have evolved subject to energetic selection pressure for stability and flexibility. Structural similarity between proteins that have gone through conformational changes can be captured effectively if flexibility is considered. Topologically unrelated proteins that preserve secondary structure packing interactions can be detected if both flexibility and Sequential permutations are considered. We propose the FlexSnap algorithm for flexible non-topological protein structural alignment. Results: The effectiveness of FlexSnap is demonstrated by measuring the agreement of its alignments with manually curated non-sequential structural alignments. FlexSnap showed competitive results against state-of-the-art algorithms, like DALI, SARF2, MultiProt, FlexProt, and FATCAT. Moreover on the DynDom dataset, FlexSnap reported longer alignments with smaller rmsd. Conclusions: We have introduced FlexSnap, a greedy chaining algorithm that reports both sequential and non-sequential alignments and allows twists (hinges). We assessed the quality of the FlexSnap alignments by measuring its agreements with manually curated non-sequential alignments. On the FlexProt dataset, FlexSnap was competitive to state-of-the-art flexible alignment methods. Moreover, we demonstrated the benefits of introducing hinges by showing significant improvements in the alignments reported by FlexSnap for the structure pairs for which rigid alignment methods reported alignments with either low coverage or large rmsd.AvailabilityAn implementation of the FlexSnap algorithm will be made available online at http://www.cs.rpi.edu/~zaki/software/flexsnap. http://www.almob.org/content/5/1/12 Saeed Salem Mohammed Zaki Chris Bystroff Algorithms for Molecular Biology 2010, 5:12 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-12 Algorithms for Molecular Biology 1748-7188 5 12 2010-01-04T00:00:00Z PDF Background: Segmental duplications, or low-copy repeats, are common in mammalian genomes. In the human genome, most segmental duplications are mosaics comprised of multiple duplicated fragments. This complex genomic organization complicates analysis of the evolutionary history of these sequences. One model proposed to explain this mosaic patterns is a model of repeated aggregation and subsequent duplication of genomic sequences. Results: We describe a polynomial-time exact algorithm to compute duplication distance, a genomic distance defined as the most parsimonious way to build a target string by repeatedly copying substrings of a fixed source string. This distance models the process of repeated aggregation and duplication. We also describe extensions of this distance to include certain types of substring deletions and inversions. Finally, we provide a description of a sequence of duplication events as a context-free grammar (CFG). Conclusion: These new genomic distances will permit more biologically realistic analyses of segmental duplications in genomes. http://www.almob.org/content/5/1/11 Crystal Kahn Shay Mozes Benjamin Raphael Algorithms for Molecular Biology 2010, 5:11 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-11 Algorithms for Molecular Biology 1748-7188 5 11 2010-01-04T00:00:00Z PDF Background: This paper considers the problem of identifying pathways through metabolic networks that relate to a specific biological response. Our proposed model, HME3M, first identifies frequently traversed network paths using a Markov mixture model. Then by employing a hierarchical mixture of experts, separate classifiers are built using information specific to each path and combined into an ensemble prediction for the response. Results: We compared the performance of HME3M with logistic regression and support vector machines (SVM) for both simulated pathways and on two metabolic networks, glycolysis and the pentose phosphate pathway for Arabidopsis thaliana. We use AltGenExpress microarray data and focus on the pathway differences in the developmental stages and stress responses of Arabidopsis. The results clearly show that HME3M outperformed the comparison methods in the presence of increasing network complexity and pathway noise. Furthermore an analysis of the paths identified by HME3M for each metabolic network confirmed known biological responses of Arabidopsis. Conclusions: This paper clearly shows HME3M to be an accurate and robust method for classifying metabolic pathways. HME3M is shown to outperform all comparison methods and further is capable of identifying known biologically active pathways within microarray data. http://www.almob.org/content/5/1/10 Timothy Hancock Hiroshi Mamitsuka Algorithms for Molecular Biology 2010, 5:10 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-10 Algorithms for Molecular Biology 1748-7188 5 10 2010-01-04T00:00:00Z PDF Background: The fingerprint of a molecule is a bitstring based on its structure, constructed such that structurally similar molecules will have similar fingerprints. Molecular fingerprints can be used in an initial phase of drug development for identifying novel drug candidates by screening large databases for molecules with fingerprints similar to a query fingerprint. Results: In this paper, we present a method which efficiently finds all fingerprints in a database with Tanimoto coefficient to the query fingerprint above a user defined threshold. The method is based on two novel data structures for rapid screening of large databases: the kD grid and the Multibit tree. The kD grid is based on splitting the fingerprints into k shorter bitstrings and utilising these to compute bounds on the similarity of the complete bitstrings. The Multibit tree uses hierarchical clustering and similarity within each cluster to compute similar bounds. We have implemented our method and tested it on a large real-world data set. Our experiments show that our method yields approximately a three-fold speed-up over previous methods. Conclusions: Using the novel kD grid and Multibit tree significantly reduce the time needed for searching databases of fingerprints. This will allow researchers to (1) perform more searches than previously possible and (2) to easily search large databases. http://www.almob.org/content/5/1/9 Thomas Kristensen Jesper Nielsen Christian Pedersen Algorithms for Molecular Biology 2010, 5:9 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-9 Algorithms for Molecular Biology 1748-7188 5 9 2010-01-04T00:00:00Z PDF Background: Supertree methods comprise one approach to reconstructing large molecular phylogenies given multi-marker datasets: trees are estimated on each marker, and then combined into a tree (the "supertree") on the entire set of taxa. Supertrees can be constructed using various algorithmic techniques, with the most common being matrix representation with parsimony (MRP). When the data allow, the competing approach is a combined analysis (also known as a "supermatrix" or "total evidence" approach) whereby the different sequence data matrices for each of the different subsets of taxa are concatenated into a single supermatrix, and a tree is estimated on that supermatrix. Results: In this paper, we describe an extensive simulation study we performed comparing two supertree methods, MRP and weighted MRP, to combined analysis methods on large model trees. A key contribution of this study is our novel simulation methodology (Super-Method Input Data Generator, or SMIDGen) that betterreflects biological processes and the practices of systematists than earlier simulations. We show that combined analysis based upon maximum likelihood outperforms MRP and weighted MRP, giving especially big improvements when the largest subtree does not contain most of the taxa. Conclusions: This study demonstrates that MRP and weighted MRP produce distinctly less accurate trees than combined analyses for a given base method (maximum parsimony or maximum likelihood). Since there are situations in which combined analyses are not feasible, there is a clear need for better supertree methods. The source tree and combined datasets used in this study can be used to test other supertree and combined analysis methods. http://www.almob.org/content/5/1/8 M. Swenson Francois Barbancon Tandy Warnow C Linder Algorithms for Molecular Biology 2010, 5:8 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-8 Algorithms for Molecular Biology 1748-7188 5 8 2010-01-04T00:00:00Z PDF Background: Two biomolecular 3-D structures are said to be similar if the RMSD (root mean square deviation) between the two molecules' sequences of 3-D coordinates is less than or equal to some given constant bound. Tools for searching for similar structures in biomolecular 3-D structure databases are becoming increasingly important in the structural biology of the post-genomic era. Results: We consider an important, fundamental problem of reporting all substructures in a 3-D structure database of chain molecules (such as proteins) which are similar to a given query 3-D structure, with consideration of indels (i.e., insertions and deletions). This problem has been believed to be very difficult but its exact computational complexity has not been known. In this paper, we first prove that the problem in unbounded dimensions is NP-hard. We then propose a new algorithm that dramatically improves the average-case time complexity of the problem in 3-D in case the number of indels k is bounded by a constant. Our algorithm solves the above problem for a query of size m and a database of size N in average-case O(N) time, whereas the time complexity of the previously best algorithm was O(Nmk+1). Conclusions: Our results show that although the problem of searching for similar structures in a database based on the RMSD measure with indels is NP-hard in the case of unbounded dimensions, it can be solved in 3-D by a simple average-case linear time algorithm when the number of indels is bounded by a constant. http://www.almob.org/content/5/1/7 Tetsuo Shibuya Jesper Jansson Kunihiko Sadakane Algorithms for Molecular Biology 2010, 5:7 2010-01-04T00:00:00Z doi:10.1186/1748-7188-5-7 Algorithms for Molecular Biology 1748-7188 5 7 2010-01-04T00:00:00Z PDF