Multiple genome comparison based on overlap regions of pairwise local alignments.

BACKGROUND: Mancheron, Uricaru and Rivals (Nucleic Acids Res. 39:e101, 2011) recently introduced a new approach in the context of multiple genome comparison that allows to detect regions of strong overlaps in a set of pairwise local alignments between several reference genomes and one target genome. Such overlap regions are an important source of information in genome annotation. RESULTS: In this paper we introduce a series of algorithms that improve over the approach of Mancheron et al., both in terms of computational complexity and in practical runtime. We also extend the problem definition such that overlaps to different reference genomes can be rated differently and regions overlapping only a subset of the reference genomes are detected.

DECOMP--from interpreting Mass Spectrometry peaks to solving the Money Changing Problem.

UNLABELLED: We introduce Decomp, a tool that computes the sum formula of all molecules whose mass equals the input mass. This problem arises frequently in biochemistry and mass spectrometry (MS), when we know the molecular mass of a protein, DNA or metabolite fragment but have no other information. A closely related problem is known as the Money Changing Problem (MCP), where all masses are positive integers. Recently, efficient algorithms have been developed for the MCP, in which Decomp applies to real-valued MS data. The excellent performance of this method on proteomic and metabolomic MS data has recently been demonstrated. Decomp has an easy-to-use graphical interface, which caters for both types of users: those interested in solving MCP instances and those submitting MS data. AVAILABILITY: Decomp is freely accessible at http://bibiserv.techfak.uni-bielefeld.de/decomp/.