MOTIVATION: Position-specific probability matrices (PPMs, also called position-specific weight matrices) have been the dominating model for transcription factor (TF)-binding motifs in DNA. There is, however, increasing recent evidence of better performance of higher order models such as Markov models of order one, also called adjacent dinucleotide matrices (ADMs). ADMs can model dependencies between adjacent nucleotides, unlike PPMs. A modeling technique and software tool that would estimate such models simultaneously both for monomers and their dimers have been missing. RESULTS: We present an ADM-based mixture model for monomeric and dimeric TF-binding motifs and an expectation maximization algorithm MODER2 for learning such models from training data and seeds. The model is a mixture that includes monomers and dimers, built from the monomers, with a description of the dimeric structure (spacing, orientation). The technique is modular, meaning that the co-operative effect of dimerization is made explicit by evaluating the difference between expected and observed models. The model is validated using HT-SELEX and generated datasets, and by comparing to some earlier PPM and ADM techniques. The ADM models explain data slightly better than PPM models for 314 tested TFs (or their DNA-binding domains) from four families (bHLH, bZIP, ETS and Homeodomain), the ADM mixture models by MODER2 being the best on average. AVAILABILITY AND IMPLEMENTATION: Software implementation is available from https://github.com/jttoivon/moder2. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We formulate and analyze a novel seed-driven algorithm SeedHam for PPM learning. To learn a PPM of length l, the algorithm uses the most frequent l-mer of the training data as a seed, and then restricts the learning into a small Hamming neighbourhood of the seed. The SeedHam method is intended for PPM learning from large sequence sets (up to hundreds of Mbases) containing enriched motif instances. A robust variant of the method is introduced that decreases contamination from artefact instances of the motif and thereby allows using larger Hamming neighbourhoods. To solve the motif orientation problem in two-stranded DNA we introduce a novel seed finding rule, based on analysis of the palindromic structure of sequences. Test experiments are reported, that illustrate the relative strengths of different variants of our methods, and show that our algorithms are fast and give stable and accurate results. Availability and implementation: A C++ implementation of the method is available from https://github.com/jttoivon/seedham/ Contact: [email protected]

Motivation: While the position weight matrix (PWM) is the most popular model for sequence motifs, there is growing evidence of the usefulness of more advanced models such as first-order Markov representations, and such models are also becoming available in well-known motif databases. There has been lots of research of how to learn these models from training data but the problem of predicting putative sites of the learned motifs by matching the model against new sequences has been given less attention. Moreover, motif site analysis is often concerned about how different variants in the sequence affect the sites. So far, though, the corresponding efficient software tools for motif matching have been lacking. Results: We develop fast motif matching algorithms for the aforementioned tasks. First, we formalize a framework based on high-order position weight matrices for generic representation of motif models with dinucleotide or general q -mer dependencies, and adapt fast PWM matching algorithms to the high-order PWM framework. Second, we show how to incorporate different types of sequence variants , such as SNPs and indels, and their combined effects into efficient PWM matching workflows. Benchmark results show that our algorithms perform well in practice on genome-sized sequence sets and are for multiple motif search much faster than the basic sliding window algorithm. Availability and Implementation: Implementations are available as a part of the MOODS software package under the GNU General Public License v3.0 and the Biopython license ( http://www.cs.helsinki.fi/group/pssmfind ). Contact: [email protected].

Motivation: New long read sequencing technologies, like PacBio SMRT and Oxford NanoPore, can produce sequencing reads up to 50 000 bp long but with an error rate of at least 15%. Reducing the error rate is necessary for subsequent utilization of the reads in, e.g. de novo genome assembly. The error correction problem has been tackled either by aligning the long reads against each other or by a hybrid approach that uses the more accurate short reads produced by second generation sequencing technologies to correct the long reads. Results: We present an error correction method that uses long reads only. The method consists of two phases: first, we use an iterative alignment-free correction method based on de Bruijn graphs with increasing length of k -mers, and second, the corrected reads are further polished using long-distance dependencies that are found using multiple alignments. According to our experiments, the proposed method is the most accurate one relying on long reads only for read sets with high coverage. Furthermore, when the coverage of the read set is at least 75×, the throughput of the new method is at least 20% higher. Availability and Implementation: LoRMA is freely available at http://www.cs.helsinki.fi/u/lmsalmel/LoRMA/ . Contact: [email protected].

The longest common substring with k-mismatches problem is to find, given two strings S1 and S2, a longest substring A1 of S1 and A2 of S2 such that the Hamming distance between A1 and A2 is ≤k. We introduce a practical O(nm) time and O(1) space solution for this problem, where n and m are the lengths of S1 and S2, respectively. This algorithm can also be used to compute the matching statistics with k-mismatches of S1 and S2 in O(nm) time and O(m) space. Moreover, we also present a theoretical solution for the k=1 case which runs in O(nlog⁡m) time, assuming m≤n, and uses O(m) space, improving over the existing O(nm) time and O(m) space bound of Babenko and Starikovskaya [1].

MOTIVATION: Assembling genomes from short read data has become increasingly popular, but the problem remains computationally challenging especially for larger genomes. We study the scaffolding phase of sequence assembly where preassembled contigs are ordered based on mate pair data. RESULTS: We present MIP Scaffolder that divides the scaffolding problem into smaller subproblems and solves these with mixed integer programming. The scaffolding problem can be represented as a graph and the biconnected components of this graph can be solved independently. We present a technique for restricting the size of these subproblems so that they can be solved accurately with mixed integer programming. We compare MIP Scaffolder to two state of the art methods, SOPRA and SSPACE. MIP Scaffolder is fast and produces better or as good scaffolds as its competitors on large genomes. AVAILABILITY: The source code of MIP Scaffolder is freely available at http://www.cs.helsinki.fi/u/lmsalmel/mip-scaffolder/. CONTACT: [email protected].

Position weight matrices are an important method for modeling signals or motifs in biological sequences, both in DNA and protein contexts. In this paper, we present fast algorithms for the problem of finding significant matches of such matrices. Our algorithms are of the online type, and they generalize classical multipattern matching, filtering, and superalphabet techniques of combinatorial string matching to the problem of weight matrix matching. Several variants of the algorithms are developed, including multiple matrix extensions that perform the search for several matrices in one scan through the sequence database. Experimental performance evaluation is provided to compare the new techniques against each other as well as against some other online and index-based algorithms proposed in the literature. Compared to the brute-force O(mn) approach, our solutions can be faster by a factor that is proportional to the matrix length m. Our multiple-matrix filtration algorithm had the best performance in the experiments. On a current PC, this algorithm finds significant matches (p = 0.0001) of the 123 JASPAR matrices in the human genome in about 18 minutes.

UNLABELLED: MOODS (MOtif Occurrence Detection Suite) is a software package for matching position weight matrices against DNA sequences. MOODS implements state-of-the-art online matching algorithms, achieving considerably faster scanning speed than with a simple brute-force search. MOODS is written in C++, with bindings for the popular BioPerl and Biopython toolkits. It can easily be adapted for different purposes and integrated into existing workflows. It can also be used as a C++ library. AVAILABILITY: The package with documentation and examples of usage is available at http://www.cs.helsinki.fi/group/pssmfind. The source code is also available under the terms of a GNU General Public License (GPL).

Over recent years, five European PhD programmes have organized a series of 'Bioinformatics Research and Education Workshops'. These workshops address the needs of first-year PhD students and have been designed to combine a maximum of educational impact and scientific stimulation with a minimum of financial and administrative effort. We describe the BREW experience and argue that this type of event constitutes an attractive component of PhD education in computational biology and beyond.

BACKGROUND: Metabolic fluxes provide invaluable insight on the integrated response of a cell to environmental stimuli or genetic modifications. Current computational methods for estimating the metabolic fluxes from 13C isotopomer measurement data rely either on manual derivation of analytic equations constraining the fluxes or on the numerical solution of a highly nonlinear system of isotopomer balance equations. In the first approach, analytic equations have to be tediously derived for each organism, substrate or labelling pattern, while in the second approach, the global nature of an optimum solution is difficult to prove and comprehensive measurements of external fluxes to augment the 13C isotopomer data are typically needed. RESULTS: We present a novel analytic framework for estimating metabolic flux ratios in the cell from 13C isotopomer measurement data. In the presented framework, equation systems constraining the fluxes are derived automatically from the model of the metabolism of an organism. The framework is designed to be applicable with all metabolic network topologies, 13C isotopomer measurement techniques, substrates and substrate labelling patterns. By analyzing nuclear magnetic resonance (NMR) and mass spectrometry (MS) measurement data obtained from the experiments on glucose with the model micro-organisms Bacillus subtilis and Saccharomyces cerevisiae we show that our framework is able to automatically produce the flux ratios discovered so far by the domain experts with tedious manual analysis. Furthermore, we show by in silico calculability analysis that our framework can rapidly produce flux ratio equations--as well as predict when the flux ratios are unobtainable by linear means--also for substrates not related to glucose. CONCLUSION: The core of 13C metabolic flux analysis framework introduced in this article constitutes of flow and independence analysis of metabolic fragments and techniques for manipulating isotopomer measurements with vector space techniques. These methods facilitate efficient, analytic computation of the ratios between the fluxes of pathways that converge to a common junction metabolite. The framework can been seen as a generalization and formalization of existing tradition for computing metabolic flux ratios where equations constraining flux ratios are manually derived, usually without explicitly showing the formal proofs of the validity of the equations.

This supplement contains extended versions of a selected subset of papers presented at the workshop PMSB 2007, Probabilistic Modeling and Machine Learning in Structural and Systems Biology, Tuusula, Finland, from June 17 to 18, 2006.

MOTIVATION: Flux estimation using isotopomer information of metabolites is currently the most reliable method to obtain quantitative estimates of the activity of metabolic pathways. However, the development of isotopomer measurement techniques for intermediate metabolites is a demanding task. Careful planning of isotopomer measurements is thus needed to maximize the available flux information while minimizing the experimental effort. RESULTS: In this paper we study the question of finding the smallest subset of metabolites to measure that ensure the same level of isotopomer information as the measurement of every metabolite in the metabolic network. We study the computational complexity of this optimization problem in the case of the so-called positional enrichment data, give methods for obtaining exact and fast approximate solutions, and evaluate empirically the efficacy of the proposed methods by analyzing a metabolic network that models the central carbon metabolism of Saccharomyces cerevisiae.

MOTIVATION: cDNA amplified fragment length polymorphism (cDNA-AFLP) is one of the few genome-wide level expression profiling methods capable of finding genes that have not yet been cloned or even predicted from sequence but have interesting expression patterns under the studied conditions. In cDNA-AFLP, a complex cDNA mixture is divided into small subsets using restriction enzymes and selective PCR. A large cDNA-AFLP experiment can require a substantial amount of resources, such as hundreds of PCR amplifications and gel electrophoresis runs, followed by manual cutting of a large number of bands from the gels. Our aim was to test whether this workload can be reduced by rational design of the experiment. RESULTS: We used the available genomic sequence information to optimize cDNA-AFLP experiments beforehand so that as many transcripts as possible could be profiled with a given amount of resources. Optimization of the selection of both restriction enzymes and selective primers for cDNA-AFLP experiments has not been performed previously. The in silico tests performed suggest that substantial amounts of resources can be saved by the optimization of cDNA-AFLP experiments.

MOTIVATION: Measuring transcriptional expression levels (transcriptional profiling) has become one of the most important methods in functional genomics. Still, new measuring methods are needed to obtain more reliable, quantitative data about transcription on a genomic scale. In this paper we concentrate on certain computational optimization problems arising in the design of one such novel method. From a computational point of view the key feature of the new method is that the hybridized probes are distinguished from each other based on their different size. Therefore the probes have to be assigned into pools such that the probes in the same pool have unique sizes different enough from each other. Identification of expressed RNA is given by probe pool and probe size while quantification is given by the label of the probe, e.g. fluorescence intensity. RESULTS: We show how to computationally find the probes and assign them into pools for a whole genome such that (i) each gene has a specific probe suitable for amplification and hybridization, and (ii) the expression level measurement can be done in a minimal number of pools separable by electrophoresis in order to minimize the total experiment cost of the measurement. Our main result is a polynomial-time approximation algorithm for assigning the probes into pools. We demonstrate the feasibility of the procedure by selecting probes for the yeast genome and assigning them into less than 100 pools. The probe sequences and their assignment into pools are available for academic research on request from the authors.

We consider the template matching problem, in which one wants to find all good enough occurrences of a pattern template P from a larger image I. The current standard of template matching is based on cross correlation computed in Fourier domain, using the fast Fourier transform (FFT). This can be extended to rotations of the template by a suitable rotational sampling of the template. An alternative approach, pursued here, is to solve the problem in the spatial domain using so-called filtering algorithms. Such algorithms scan the image quickly and find all promising areas for a more accurate (but slower) examination such that no good enough occurrences of the template are lost. The paper shows that the filtering approach can be orders of magnitude faster than the FFT based method. Especially in the 3D case the FFT is intolerably slow.

We consider the problem of defining and evaluating the distance between a three-dimensional pattern P[1..m, 1..m, 1..m] of voxels and a three-dimensional volume V[1..n, 1..n, 1..n] of voxels when rotations of P are also allowed. In particular we are interested in finding the orientation and location of P with respect of V that gives the minimum distance. We consider several distance measures. Our basic method works for all distance measures such that the voxels affect the distance between P and V only locally, that is, the distance between two voxels can be completed in unit time. The number of different orientations that P can have is analyzed. We give incremental algorithms to compute the distance, and several filtering algorithms to compute the upper and lower bounds for the distance. We conclude with experimental results on real data (three dimensional reconstruction of a biological virus).

Algorithms with optimal expected running time are presented for searching the occurrences of a two-dimensional mX m pattern P in a two-dimensional n X n text T over an alphabet of size c. The algorithms are based on placing in the text a static grid of test points, determined only by n, m, and c (not dynamically by earlier test results). Using test strings read from the test points the algorithms eliminate as many potential occurrences of P as possible. The remaining potential occurrences are separately checked for actual occurrences. A suitable choice of the test point set leads to algorithms with expected running time O(n 2 log c m 2 /m 2 ) using the uniform Bernoulli model of randomness. This is shown to be optimal by a generalization of a one-dimensional lower bound result by Yao. Experimental results show that the algorithms are efficient in practice, too. The method is also generalized for the k mismatches problem. The resulting algorithm has expected running time O(kn 2 log c m 2 /m 2 ), provided that $k\leq(m\lfloor m/\lceil\log_c m^2\rceil\rfloor-1)/2$.\ All algorithms need preprocessing of P which takes time and space O(m 2 ). The text processing can be done on-line, using a rather small window. The algorithms easily generalize to d-dimensional matching for any d.

On the one hand, the inclusion problem for nonerasing and erasing pattern languages is undecidable (see Jiang et al., 1995). On the other hand, the language equivalence problem for nonerasing pattern languages is trivially decidable (see Angluin, 1980) but the question of whether the same holds for erasing pattern languages is still open. It has been conjectured by Jiang et al. that the language equivalence problem for erasing pattern languages is also decidable. In this paper, we introduce a new normal form for patterns and show, using the normal form, that the language equivalence problem for erasing pattern languages is decidable in many special cases. We conjecture that our normal form procedure decides the problem in the general case, too. If the conjecture holds true, then the normal form is the shortest pattern generating a given erasing pattern language.

Experimental comparisons of the running time of approximate string matching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k, the task is to find all approximate occurrences of the pattern in the text with at most k differences (insertions, deletions, changes). We consider seven algorithms based on different approaches including dynamic programming, Boyer–Moore string matching, suffix automata, and the distribution of characters. It turns out that none of the algorithms is the best for all values of the problem parameters, and the speed differences between the methods can be considerable.

In order to enable the database programmer to reason about relations over strings of arbitrary length we introduce alignment logic, a modal extension of relational calculus. In addition to relations, a state in the model consists of a two-dimensional array where the strings are aligned on top of each other. The basic modality in the language (a transpose, or “slide”) allows for a rearrangement of the alignment, and more complex formulas can be formed using a syntax reminiscent of regular expressions, in addition to the usual connectives and quantifiers. It turns out that the computational counterpart of the string-based portion of the logic is the class of multitape two-way finite state automata, which are devices particularly well suited for the implementation of string matching. A computational counterpart of the full logic is obtained from relational algebra by extending the selection operator into filters based on these multitape machines. Safety of formulas in alignment logic implies that new strings generated from old ones have to be of bounded length. While an undecidable property in general, this boundedness is decidable for an important subclass of formulas. As far as expressive power is concerned, alignment logic includes previous proposals for querying string databases, and gives full Turing computability. The language can be restricted to define exactly regular sets and sets in the polynomial hierarchy.

The Boyer–Moore idea applied in exact string matching is generalized to approximate string matching. Two versions of the problem are considered. The k mismatches problem is to find all approximate occurrences of a pattern string (length m) in a text string (length n) with at most k mismatches. The generalized Boyer–Moore algorithm is shown (under a mild independence assumption) to solve the problem in expected time $O(kn({1 / {(m - k) + ({k / c})}}))$, where c is the size of the alphabet. A related algorithm is developed for the k differences problem, where the task is to find all approximate occurrences of a pattern in a text with $ \leqslant k$ differences (insertions, deletions, changes). Experimental evaluation of the algorithms is reported, showing that the new algorithms are often significantly faster than the old ones. Both algorithms are functionally equivalent with the Horspool version of the Boyer–Moore algorithm when $k = 0$.

We present an algorithm for learning sets of rules that are organized into up to k levels. Each level can contain an arbitrary number of rules "if c then l" where l is the class associated to the level and c is a concept from a given class of basic concepts. The rules of higher levels have precedence over the rules of lower levels and can be used to represent exceptions. As basic concepts we can use Boolean attributes in the infinite attribute space model, or certain concepts defined in terms of substrings. Given a sample of m examples, the algorithm runs in polynomial time and produces a consistent concept representation of size O((log m) k n k ), where n is the size of the smallest consistent representation with k levels of rules. This implies that the algorithm learns in the PAC model. The algorithm repeatedly applies the greedy heuristics for weighted set cover. The weights are obtained from approximate solutions to previous set cover problems. Key words: computational learni...

The problem of testing whether or not a context-free grammar possesses the LALR(k) property is studied.For each fixed integer k -> 1 (i e, only the subject grammar is a problem parameter) the problem ts shown to be complete for polynounal space (PSPACE) For free k (i.e., both the grammar and the integer k are problem parameters) the problem ~s shown to be PSPACE-complete when k is expressed m unary and complete for nondetermuustic one-level exponential tune (NE) when k is expressed in binary.The PSPACE-hardness results are obtained by a reduction from the l'mite automaton nonuniversality problem, whereas the upper bound results are obtained by an economic nondeterministic algorithm that uses only linear space when k is fixed and quadratic space when k is in unary.The lower bound result for fixed k > 1 is in contrast with the complexity of testing the membership in several other easily parsed classes of grammars, such as LR(k), SLK(k), LC(k), LL(k), and strong LL(k) grammars, for which determmlsUc polynomtal-tune tests are known.The upper-bound results for free k m turn demonstrate how the complexity of the membership testing problems is dominated by k: for k in unary LALR(k) testing is no harder (with respect to polynomml-ttme reductions) than LALR(I) testing, and for k in binary no harder than, for example, strong LL(k) testing (which is known to be NE-complete).

Inspired by the recent solution of the Berman-Hartmanis conjecture [SIAM J. Comp., 6 (1977), pp. 305–322] that NP cannot have a sparse complete set for many-one reductions unless ${\text{P}} = {\text{NP}}$, we analyze the implications of NP and PSPACE having sparse, hard or complete sets for reduction types more general than the many-one reductions. Three special cases of truth-table reductions are considered. First we show that if NP (PSPACE) has a tally $ \leqq _{k - T}^P $-hard set, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$. Here $ \leqq _{k - T}^P $ denotes a subcase of polynomial time Turing reducibility in which, for some constant k, the reducing Turing machine is allowed to make at most k queries to the oracle. We also show that if co-NP (PSPACE) has a sparse hard set for conjunctive polynomial time reductions, then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$.

A generalizauon of the alternate stacking procedure of Valiant for decidmg the eqmvalence of some determuusuc pushdown automata (dpda) Is introduced.To analyze the power of the generalized procedure, a subclass of dpdas, called the proper dpdas, is defined.This class properly contains the nonsingular dpdas and the real-time strict dpdas, and the corresponding class of languages properly contains the real-tune strict determmlsttc languages.The generalized procedure is shown to yield an equivalence test for proper dpdas, at least one of which ~s also a fuute-turn machine.It is also shown that the equivalence problem for proper automata is reducible to the problem of deodmg whether or not an automaton ~s proper.

The problem of testing whether or not an arbitrary context-free grammar is LALR(k) for a fixed integer k ≥ 1 (i.e. only the subject grammar is a problem parameter) is shown to be PSPACE-complete. The result is in contrast with testing the membership in several other easily parsed classes of grammars, such as LR(k), SLR(k), LC(k) and LL(k) grammars, for which deterministic polynomial time membership tests are known. The PSPACE-hardness of the problem is proved using a transformation from the finite state automaton non-universality problem. A nondeterministic algorithm for constructing sets of LR(k) items leads to a polynomially space bounded algorithm for LALR(k) testing.

The problem of constructing multi-pass evaluators for attribute grammars is studied. We show that the construction algorithm used heretofore can in the worst case produce evaluators which perform $2n - 1$ passes over the parse tree, where n is the minimum number of passes required. Furthermore, the problem of constructing an optimal evaluation order is shown to be NP-complete. We then develop a new characterization for attribute grammars evaluable in passes. It can be directly applied as an efficient membership test. Finally, the characterization is used for deriving a polynomial time construction algorithm for a large subclass of pass-oriented attribute grammars. The subclass is argued to be of practical importance.

EffectsSome methods for computer-aided analysis of numerical stability requLre a computation of weighted sums of the form ~h(oR,/O6h) • (oR,/~h) • ah.Here R, and R: are result quantitms (real numbers) of the numerical program P being analyzed, and the partial derivatives are with respect to roundoff or data errors 8h Each weight ah m a real number, which depends on the analysis techmque.A method m given for evaluating such sums directly without first exphcltly computing partml derivatives OR,/ 08h The method applms to analyzing single-output programs as well as multiple-output ones The data storage reqmred for the method m O (p2), where p is the storage used by P. The time requirement is O(mp), where m is the number of arithmetic operatmns m the partmular executmn of P bemg analyzed The storage reqmrement m thus independent of m, whmh facilitates efficmnt Implementation of the method Key Words and Phrases automatic roundoff analysis, numerical stability, numerical linear algebra CR Categories 5 11, 5.14

A generalization of the alternate stacking procedure of Valiant for deciding the equivalence of some deterministic pushdown automata (dpda) is introduced. To analyze the power of the generalized procedure we define a subclass of dpda's, called the proper dpda's. This class properly contains the non-singular dpda's and the real time strict dpda's, and the corresponding class of languages properly contains the real time strict deterministic languages. The equivalence problem for proper automata is reducible to the problem of deciding whether or not an automaton is proper. The main result of the paper is that the generalized procedure yields an equivalence test for proper dpda's, at least one of which is also a finite-turn machine.