Biomedical subjects

Michal Ziv-Ukelson

Publications and source records attributed to Michal Ziv-Ukelson.

4 recordsLinked to original sources

PubMed2006

On the complexity of sparse exon assembly.

Gene structure prediction is one of the most important problems in computational molecular biology. It involves two steps: the first is finding the evidence (e.g., predicting splice sites) and the second is interpreting the evidence, that is, trying to determine the whole gene structure by assembling its pieces. In this paper, we suggest a combinatorial solution to the second step, which is also referred to as the "Exon Assembly Problem." We use a similarity-based approach that aims to produce a single gene structure based on similarities to a known homologous sequence. We target the sparse case, where filtering has been applied to the data, resulting in a set of O(n) candidate exon blocks. Our algorithm yields an O(n(2) square root of n) solution.

Algorithms↗

PubMed2006

On the repeat-annotated phylogenetic tree reconstruction problem.

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals (i.e., inversions) and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process--including both the tree-topology as well as internal node genome orders--is uniquely determined, a property that is of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR).

Algorithms↗

PubMed2006

A high-throughput approach for associating MicroRNAs with their activity conditions.

Plant microRNAs (miRNAs) are short RNA sequences that bind to target mRNAs and change their expression levels by redirecting their stabilities and marking them for cleavage. In Arabidopsis thaliana, microRNAs have been shown to regulate development and are believed to impact expression both under various conditions, such as stress and stimuli, as well as in specific tissue types. We present a high throughput approach for associating between microRNAs and conditions in which they act, using novel statistical and algorithmic techniques. Our new tool, miRNAXpress, at first computes a (binary) matrix T denoting the potential targets of microRNAs. Then, using T and an additional predefined matrix X indicating expression of genes under various conditions, it produces a new matrix that predicts associations between microRNAs and the conditions in which they act. Thus, the program comprises two main modules that work in tandem to compute the desired output. The first is an efficient target prediction engine that predicts mRNA targets of query microRNAs by evaluating the optimal duplex that could be formed between the two: given a short query RNA, a long target RNA, and a predefined energy cut-off threshold, the program finds and reports all putative binding sites of the query RNA in the target RNA with hybridization energy bounded by the predefined threshold. The second module realizes an association operation that is computed by a method which relies on an efficient t-test to compute the associations. The calculation of the matrix of microRNAs and their potential targets is the computationally intensive part of the work done by miRNAXpress, and therefore an efficient algorithm for this portion facilitates the entire process. Thus, the target prediction engine is based on an efficient approximate hybridization search algorithm whose efficiency is the result of utilizing the sparsity of the search space without sacrificing the optimality of the results. The time complexity of this algorithm is almost linear in the size of a sparse set of locations where base-pairs are stacked at a height of three or more. Thus miRNAXpress is a novel tool for associating between microRNAs and the conditions in which they act. We employed it to conduct a study, using the plant Arabidopsis thaliana as our model organism. By applying miRNAXpress to 98 microRNAs and 380 conditions, some biologically interesting and statistically strong relations were discovered. For example, mir159C activity is possibly a factor in the misresponse of nph4 mutants to phototropic stimulations.

Arabidopsis↗

PubMed2005

Alignment of metabolic pathways.

MOTIVATION: Several genome-scale efforts are underway to reconstruct metabolic networks for a variety of organisms. As the resulting data accumulates, the need for analysis tools increases. A notable requirement is a pathway alignment finder that enables both the detection of conserved metabolic pathways among different species as well as divergent metabolic pathways within a species. When comparing two pathways, the tool should be powerful enough to take into account both the pathway topology as well as the nodes' labels (e.g. the enzymes they denote), and allow flexibility by matching similar--rather than identical--pathways. RESULTS: MetaPathwayHunter is a pathway alignment tool that, given a query pathway and a collection of pathways, finds and reports all approximate occurrences of the query in the collection, ranked by similarity and statistical significance. It is based on a novel, efficient graph matching algorithm that extends the functionality of known techniques. The program also supports a visualization interface with which the alignment of two homologous pathways can be graphically displayed. We employed this tool to study the similarities and differences in the metabolic networks of the bacterium Escherichia coli and the yeast Saccharomyces cerevisiae, as represented in highly curated databases. We reaffirmed that most known metabolic pathways common to both the species are conserved. Furthermore, we discovered a few intriguing relationships between pathways that provide insight into the evolution of metabolic pathways. We conclude with a description of biologically meaningful meta-queries, demonstrating the power and flexibility of our new tool in the analysis of metabolic pathways.

Animals↗