BACKGROUND: In 2004, Bejerano et al. announced the startling discovery of hundreds of "ultraconserved elements", long genomic sequences perfectly conserved across human, mouse, and rat. Their announcement stimulated a flurry of subsequent research. RESULTS: We generalize the notion of ultraconserved element in a natural way from extraordinary human-rodent conservation to extraordinary conservation over an arbitrary set of species. We call these "Extremely Conserved Elements". There is a linear time algorithm to find all such Extremely Conserved Elements in any multiple sequence alignment, provided that the conservation is required to be across all the aligned species. For the general case of conservation across an arbitrary subset of the aligned species, we show that the question of whether there exists an Extremely Conserved Element is NP-complete. We illustrate the linear time algorithm by cataloguing all 177 Extremely Conserved Elements in the currently available 44-vertebrate whole-genome alignment, and point out some of the characteristics of these elements. CONCLUSIONS: The NP-completeness in the case of conservation across an arbitrary subset of the aligned species implies that it is unlikely an efficient algorithm exists for this general case. Despite this fact, for the interesting case of conservation across all or most of the aligned species, our algorithm is efficient enough to be practical. The 177 Extremely Conserved Elements that we catalog demonstrate many of the characteristics of the original ultraconserved elements of Bejerano et al.

Co-expression networks are routinely used to study human diseases like obesity and diabetes. Systematic comparison of these networks between species has the potential to elucidate common mechanisms that are conserved between human and rodent species, as well as those that are species-specific characterizing evolutionary plasticity. We developed a semi-parametric meta-analysis approach for combining gene-gene co-expression relationships across expression profile datasets from multiple species. The simulation results showed that the semi-parametric method is robust against noise. When applied to human, mouse, and rat liver co-expression networks, our method out-performed existing methods in identifying gene pairs with coherent biological functions. We identified a network conserved across species that highlighted cell-cell signaling, cell-adhesion and sterol biosynthesis as main biological processes represented in genome-wide association study candidate gene sets for blood lipid levels. We further developed a heterogeneity statistic to test for network differences among multiple datasets, and demonstrated that genes with species-specific interactions tend to be under positive selection throughout evolution. Finally, we identified a human-specific sub-network regulated by RXRG, which has been validated to play a different role in hyperlipidemia and Type 2 diabetes between human and mouse. Taken together, our approach represents a novel step forward in integrating gene co-expression networks from multiple large scale datasets to leverage not only common information but also differences that are dataset-specific.

Multiple sequence alignments have wide applicability in many areas of computational biology, including comparative genomics, functional annotation of proteins, gene finding, and modeling evolutionary processes. Because of the computational difficulty of multiple sequence alignment and the availability of numerous tools, it is critical to be able to assess the reliability of multiple alignments. We present a tool called StatSigMA to assess whether multiple alignments of nucleotide or amino acid sequences are contaminated with one or more unrelated sequences. There are numerous applications for which StatSigMA can be used. Two such applications are to distinguish homologous sequences from nonhomologous ones and to compare alignments produced by various multiple alignment tools. We present examples of both types of applications.

BACKGROUND: Multiple alignment of homologous DNA sequences is of great interest to biologists since it provides a window into evolutionary processes. At present, the accuracy of whole-genome multiple alignments, particularly in noncoding regions, has not been thoroughly evaluated. RESULTS: We evaluate the alignment accuracy of certain noncoding regions using noncoding RNA alignments from Rfam as a reference. We inspect the MULTIZ 17-vertebrate alignment from the UCSC Genome Browser for all the human sequences in the Rfam seed alignments. In particular, we find 638 instances of chimeric and partial alignments to human noncoding RNA elements, of which at least 225 can be improved by straightforward means. As a byproduct of our procedure, we predict many novel instances of known ncRNA families that are suggested by the alignment. CONCLUSION: MULTIZ does a fairly accurate job of aligning these genomes in these difficult regions. However, our experiments indicate that better alignments exist in some regions.

Noncoding RNAs (ncRNAs) are important functional RNAs that do not code for proteins. We present a highly efficient computational pipeline for discovering cis-regulatory ncRNA motifs de novo. The pipeline differs from previous methods in that it is structure-oriented, does not require a multiple-sequence alignment as input, and is capable of detecting RNA motifs with low sequence conservation. We also integrate RNA motif prediction with RNA homolog search, which improves the quality of the RNA motifs significantly. Here, we report the results of applying this pipeline to Firmicute bacteria. Our top-ranking motifs include most known Firmicute elements found in the RNA family database (Rfam). Comparing our motif models with Rfam's hand-curated motif models, we achieve high accuracy in both membership prediction and base-pair-level secondary structure prediction (at least 75% average sensitivity and specificity on both tasks). Of the ncRNA candidates not in Rfam, we find compelling evidence that some of them are functional, and analyze several potential ribosomal protein leaders in depth.

BACKGROUND: This paper addresses the problem of discovering transcription factor binding sites in heterogeneous sequence data, which includes regulatory sequences of one or more genes, as well as their orthologs in other species. RESULTS: We propose an algorithm that integrates two important aspects of a motif's significance - overrepresentation and cross-species conservation - into one probabilistic score. The algorithm allows the input orthologous sequences to be related by any user-specified phylogenetic tree. It is based on the Expectation-Maximization technique, and scales well with the number of species and the length of input sequences. We evaluate the algorithm on synthetic data, and also present results for data sets from yeast, fly, and human. CONCLUSIONS: The results demonstrate that the new approach improves motif discovery by exploiting multiple species information.

Phylogenetic footprinting is an increasingly popular comparative genomics method for detecting regulatory elements in DNA sequences. With the profusion of possible methods to use for phylogenetic footprinting, the biologist needs some guidance to choose the most appropriate tool. We present methods for comparing tools on phylogenetic footprinting data. More specifically, we discuss two different classes of comparative experiments: those on simulated data and those on real orthologous promoter regions. We then report the results of a series of such empirical comparisons. The tools compared are the alignment-based methods using ClustalW and Dialign, and the motif-finding programs MEME and FootPrinter. Our results show that methods taking the species' phylogenetic relationships into consideration obtain better accuracy.

We compare the accuracy of three motif-finding algorithms for the discovery of novel transcription factor binding sites among co-regulated genes. One of the algorithms (YMF) uses a motif model tailored for binding sites and an enumerative search of the motif space, while the other two (MEME and AlignACE) use a more general motif model and local search techniques. The comparison is done on synthetic data with planted motifs, as well as on real data sets of co-regulated genes from the yeast S. cerevisiae. More often than not, the enumerative algorithm is found to be more accurate than the other two on the yeast data sets, though there is a noticeable exclusivity in the accuracy of the different algorithms. The experiments on synthetic data reveal, not surprisingly, that each algorithm outperforms the others when motifs are planted according to its motif model.

MOTIVATION: Oligo arrays are important experimental tools for the high throughput measurement of gene expression levels. During production of oligo arrays, it is important to identify any faulty manufacturing step. RESULTS: We describe a practical algorithm for the construction of optimal quality control designs that identify any faulty manufacturing step. The algorithm uses hillclimbing, a search technique from combinatorial optimization. We also present the results of using this algorithm on all practical quality control design sizes. AVAILABILITY: On request from the authors.

Pevzner and Sze [23] considered a precise version of the motif discovery problem and simultaneously issued an algorithmic challenge: find a motif M of length 15, where each planted instance differs from M in 4 positions. Whereas previous algorithms all failed to solve this (15,4)-motif problem. Pevzner and Sze introduced algorithms that succeeded. However, their algorithms failed to solve the considerably more difficult (14,4)-, (16,5)-, and (18,6)-motif problems.We introduce a novel motif discovery algorithm based on the use of random projections of the input's substrings. Experiments on simulated data demonstrate that this algorithm performs better than existing algorithms and, in particular, typically solves the difficult (14,4)-, (16,5)-, and (18,6)-motif problems quite efficiently. A probabilistic estimate shows that the small values of d for which the algorithm fails to recover the planted (l, d)-motif are in all likelihood inherently impossible to solve. We also present experimental results on realistic biological data by identifying ribosome binding sites in prokaryotes as well as a number of known transcriptional regulatory motifs in eukaryotes.

In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo arrays leads to a combinatorial problem, requiring certain binary codes which have an additional balance property. Constructions using block designs and packings for these codes, within a range of interest in a practical manufacturing application, are developed. The focus is on equireplicate codes, constant weight codes in which every bit position is a one equally often.

We prove a time-space tradeoff for traversing undirected graphs, using a structured model that is a nonjumping variant of Cook and Rackoff's "jumping automata for graphs."

Article An algorithm for finding novel gapped motifs in DNA sequences Share on Authors: Emily Rocke Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WAView Profile , Martin Tompa Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WA Department of Computer Science and Engineering, Box 352350, University of Washington, Seattle, WAView Profile Authors Info & Claims RECOMB '98: Proceedings of the second annual international conference on Computational molecular biologyMarch 1998 Pages 228–233https://doi.org/10.1145/279069.279119Online:01 March 1998Publication History 16citation444DownloadsMetricsTotal Citations16Total Downloads444Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one.

This paper introduces communicating branching programs and develops a general technique for demonstrating communication-space tradeoffs for pairs of communicating branching programs. This technique is then used to prove communication-space tradeoffs for any pair of communicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. As an example, any pair of communicating Boolean branching programs that computes matrix-vector products over ${\text{GF}}(2)$ requires communication-space product $\Omega (n^2 )$, provided the space used is $o({n / {\log n}})$. These are the first examples of communication-space tradeoffs on a completely general model of communicating processes.

Universal traversal sequences for cycles require length $\Omega (n^{1.29} )$, improving the previous bound of $\Omega (n\log n)$. For $d \geq 3$, universal traversal sequences for d-regular graphs require length $\Omega (d^{0.71} n^{2.29} )$. For constant d, the best previous bound was $\Omega (n^2 \log n)$.

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A.Z. Broder et al. (1989). The models used are variants of S.A. Cook and C.W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated.>

Communicating branching programs are introduced, and a general technique for demonstrating communication-space tradeoffs for pairs of communicating branching programs is developed. The technique is used to prove communication-space tradeoffs for any pair of communicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. For example any pair of communicating Boolean branching programs that computes matrix-vector products over GF(2) requires communication-space product Omega (n/sup 2/). These are the first examples of communication-space tradeoffs on a completely general model of communicating processes.>

Universal traversal sequences for d-regular n-vertex graphs require length Ω(d2n2 + dn2 log n/d), for 3 ≤ d ≤ n/3 - 2. This is nearly tight for d = Θ(n). We also introduce and study several variations on the problem, e.g. edge-universal traversal sequences, showing how improved lower bounds on these would improve the bounds given above.

This paper initiates the study of communication complexity when the processors have limited work space. The following tradeoffs between number C of communications steps and space S are proved:

Following the recent independent proofs of Immerman [SIAM J. Comput., 17 (1988), pp. 935–938] and Szelepcsenyi [Bull. European Assoc. Theoret. Comput. Sci., 33 (1987), pp. 96–100] that nondeterministic space-bounded complexity classes are closed under complementation, two further applications of the inductive counting technique are developed. First, an errorless probabilistic algorithm for the undirected graph s-t connectivity problem that runs in $O(\log n)$ space and polynomial expected time is given. Then it is shown that the class LOGCFL is closed under complementation. The latter is a special case of a general result that shows closure under complementation of classes defined by semi-unbounded fan-in circuits (or, equivalently, nondeterministic auxiliary pushdown automata or tree-size bounded alternating Turing machines). As one consequence, it is shown that small numbers of “role switches” in two-person pebbling can be eliminated.

Previous article Full AccessErratum: Two Applications of Indctive Counting for Complementation ProblemsAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin TompaAllan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompahttps://doi.org/10.1137/0218084PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Erratum: Two Applications of Indctive Counting for Complementation Problems." SIAM Journal on Computing, 18(6), p. 1283[1] Allan Borodin, , Stephen A. Cook, , Patrick W. Dymond, , Walter L. Ruzzo and , Martin Tompa, Two applications of inductive counting for complementation problems, SIAM J. Comput., 18 (1989), 559–578 10.1137/0218038 90k:68049a 0678.68031 LinkISIGoogle Scholar[2] John Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput., 6 (1977), 675–695 10.1137/0206049 57:4616 0366.02024 LinkISIGoogle Scholar[3] Hermann Jung, On probabilistic time and spaceAutomata, languages and programming (Nafplion, 1985), Lecture Notes in Comput. Sci., Vol. 194, Springer, Berlin, 1985, 310–317 87b:68039 0599.68043 CrossrefGoogle Scholar Previous article FiguresRelatedReferencesCited byDetails Dual VP Classes23 September 2016 | computational complexity, Vol. 26, No. 3 Cross Ref Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages Cross Ref Computational Complexity Cross Ref Trading Space for Time in Undirected s-t ConnectivityAndrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, and Eli Upfal31 July 2006 | SIAM Journal on Computing, Vol. 23, No. 2AbstractPDF (1266 KB)My favorite ten complexity theorems of the past decade1 June 2005 Cross Ref Lower bounds on the length of universal traversal sequencesJournal of Computer and System Sciences, Vol. 45, No. 2 Cross Ref A very hard log space counting class Cross Ref Volume 18, Issue 6| 1989SIAM Journal on Computing History Submitted:03 August 1989Accepted:30 August 1989Published online:13 July 2006 InformationCopyright © 1989 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0218084Article page range:pp. 1283-1283ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined by Dymond and Tompa [J. Comput. System Sci., 30 (1985), pp. 149–161] and is used to characterize two natural parallel complexity classes, namely LOGCFL and ${\text{AC}}^1 $. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well-known results of complexity theory.

Modular integer exponentiation (given a, e, and m , compute a e mod m ) is a fundamental problem in algebraic complexity for which no efficient parallel algorithm is known. Two closely related problems are modular polynomial exponentiation (given a ( x ), e , and m ( x ), compute ( a ( x )) e mod m ( x )) and polynomial exponentiation (given a ( x ), e . and t , compute the coefficient of x t in ( a ( x )) e ). It is shown that these latter two problems are in NC 2 when a ( x ) and m ( x ) are polynomials over a finite field whose characteristic is polynomial in the input size.

The following three problems concerning random graphs can be solved in (log n)O(1) expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

The notion of a zero knowledge interactive proof that one party "knows" some secret information is explored. It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort. The zero knowledge interactive proofs for graph isomorphism, quadratic residuosity, and "knowledge" of discrete logarithms all follow as special cases. Based on these results, new zero knowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*. None of these proofs relies on any unproven assumptions.

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined in [DT85] and is used to characterize two natural parallel complexity classes, namely LOGCFL and AG1. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well known results of complexity theory.

Article Free Access Share on The parallel complexity of exponentiating polynomials over finite fields Authors: F E Fich Department of Computer Science, FR-35, University of Washington, Seattle, WA Department of Computer Science, FR-35, University of Washington, Seattle, WAView Profile , M Tompa Department of Computer Science, FR-35, University of Washington, Seattle, WA Department of Computer Science, FR-35, University of Washington, Seattle, WAView Profile Authors Info & Claims STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingDecember 1985 Pages 38–47https://doi.org/10.1145/22145.22150Online:01 December 1985Publication History 6citation246DownloadsMetricsTotal Citations6Total Downloads246Last 12 Months8Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This work generalizes decision trees in order to study lower bounds on the running times of algorithms that allow probabilistic, nondeterministic, or alternating control. It is shown that decision trees that are allowed internal randomization (at the expense of introducing a small probability of error) run no faster asymptotically than ordinary decision trees for a collection of natural problems. Two geometric techniques from the literature for proving lower bounds on the time required by ordinary decision trees are shown to be special cases of one unified technique that, in fact, applies to nondeterministic decision trees as well. Finally, it is shown that any lower bound on alternating decision tree time also applies to alternating Turing machine time.

A generalization of Dobkin and Lipton’s element uniqueness problem is introduced. For any fixed undirected graph G on vertex set $\{ v _1 , v_2 , \cdots , v_n \} $, the problem is to determine, given n real numbers $x_1 ,x_2 , \cdots ,x_n $, whether $x_i \ne x_j $ for every edge $\{ \upsilon _i ,\upsilon _j \} $ in G. This problem is shown to have upper and lower bounds of $\Theta (n\log n)$ linear comparisons if G is any dense graph. The proof of the lower bound involves showing that any dense graph must contain a subgraph with many Hamiltonian paths, and demonstrating the relevance of these Hamiltonian paths to a geometric argument. In addition, we exhibit relatively sparse graphs for which the same lower bound holds, and relatively dense graphs for which a linear upper bound holds.

This paper presents the new speedups DTIME(T) @@@@ ATIME(T/log T) and DTIME(T) @@@@ PRAM-Time(@@@@T). These improve the results of Hopcroft, Paul, and Valiant that DTIME(T) @@@@ DSPACE(T/log T), and of Paul and Reischuk that DTIME(T) @@@@ ATIME(T log log T/log T). The new approach unifies not only these two previous results, but also the result of Paterson and Valiant that Size(T) @@@@ Depth(O(T/log T)).

This work generalizes decision trees in order to model algorithms which allow probabilistic, nondeterministic, or alternating control. Two geometric techniques for proving lower bounds on the time required by ordinary decision trees (Dobkin and Lipton's “region-counting” technique as applied to the knapsack and element uniqueness problems [1], and Reingold's technique as applied to set equality [4]) are shown to be special cases of one unified technique, which in fact applies to nondeterministic decision trees as well. This technique is applied to yield tight upper and lower bounds on the nondeterministic time for solving element uniqueness, set disjointness, set membership, set equality, ε-closeness [2], and knapsack problems, as well as many of these problems complements.

This paper studies two aspects of the power of space-bounded probabilistic Turing machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. Section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic Turing machine with small error; this is a generalization of Gill's result that any language in NSPACE(log n) can be recognized by such a machine

Any Boolean straight-line program which computes the transitive closure of an $n \times n$ Boolean matrix by successive squaring requires time exceeding any polynomial in n if the space used is $o(n)$. This is the first demonstration of a “natural” algorithm which (1) has a polynomial time implementation and (2) has a small (e.g., $O(\log ^2 n)$) space implementation, but (3) has no implementation running in polynomial time and small space simultaneously. It is also shown that any implementation of Warshall’s transitive closure algorithm requires $\Omega (n)$ space, and that many familiar sorting algorithms exhibit similar behavior.

A generalization of Dobkin and Lipton's element uniqueness problem is introduced: for any fixed undirected graph G on vertex set {v1, v2, ..., vn}, the problem is to determine, given n real numbers x1, x2, ..., xn, whether xi ≠ xj for every edge {vi, vj} in G. This problem is shown to have upper and lower bounds of Θ(nlogn) linear comparisons if G is any dense graph. The proof of the lower bound involves showing that any dense graph must contain a subgraph with many Hamiltonian paths, and demonstrating the relevance of these Hamiltonian paths to a geometric argument. In addition, we exhibit relatively sparse graphs for which the same lower bound holds, and relatively dense graphs for which a linear upper bound holds.

A wire-routing problem which arises commonly in the layout of circuits for very large scale integration (VLSI) is discussed. Given the coordinates of terminals u1, u2, ..., un of one component and v1, v2, ..., vn of another, the problem is to lay out n wires so that the ith wire connects ui to vi, and adjacent wires are separated at least by some fixed distance. The solution with minimum wire length is characterized, and an optimal algorithm which constructs it is presented.

Any Boolean straight-line program which computes the transitive closure of an nxn Boolean matrix by successive squaring requires time exceeding any polynomial in n if the space used is o(n). This is the first demonstration of a “natural” algorithm which (1) has a polynomial time implementation and (2) has a small (e.g., O(log2n)) space implementation, but (3) has no implementation running in polynomial time and small space simultaneously. It is also shown that any implementation of Warshall's transitive closure algorithm requires Ω(n) space.

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

Recent research has investigated time-space tradeoffs for register allocation strategies of certain fixed sets of expressions. This paper is concerned with the time-space tradeoff for register allocation strategies of any set of expressions which compute given functions. Time-space tradeoffs for pebbling superconcentrators and grates are developed. Corollaries which follow include tradeoffs for any straight-line program which computes polynomial multiplication, polynomial convolution, the discrete Fourier transform, oblivious merging, and most sets of linear forms.