A 1.5-Approximation Algorithm for Sorting by Transpositions and (2004)
One of the most promising ways to determine evolutionary distance between two organisms is to compare the order of appearance of orthologous genes in their genomes. The resulting genome rearrangement...
Towards Optimally Multiplexed Applications of Universal Arrays (2004)
Amir Ben-dor, Tzvika Hartman, Richard M. Karp, Benno Schwikowski, Roded Sharan, Zohar Yakhini
We study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (SNPs) are to be genotyped using a universal DNA tag array. The problem of optimizing the...
A 1.5-Approximation Algorithm for Sorting by (2004)
One of the most promising ways to determine evolutionary distance between two organisms is to compare the order of appearance of orthologous genes in their genomes. The resulting genome rearrangement...
A Simpler and Faster 1.5-Approximation Algorithm for Sorting by (2004)
An important problem in genome rearrangements is sorting permutations by transpositions. Its complexity is still open, and two rather complicated 1.5-approximation algorithms for sorting linear...
On the Distribution of the Number of (2003)
Weak designs were defined in R. Raz, O. Reingold, and S. Vadhan [Extracting all the randomness and reducing the error in Trevisan's extractors, Proc 31st ACM Symp Theory of Computing, Atlanta, GA,...
A Simpler 1.5-Approximation Algorithm for Sorting By Transpositions (2003)
An important problem in genome rearrangements is sorting permutations by transpositions. Its complexity is still open, and two rather complicated 1.5-approximation algorithms for sorting linear...
Towards Optimally Multiplexed Applications of Universal (2003)
Amir Ben-dor, Tzvika Hartman, Benno Schwikowski, Roded Sharan, Zohar Yakhini
We study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (SNPs) are to be genotyped using a universal DNA tag array. The problem of optimizing the...
Enumerating Optimal Sequences of Reversals: Tools and (2002)
Cedric Chauve, Tzvika Hartman, Karine St-onge
Introduction The genome of a species can be thought of as a set of ordered sequences of genes { the ordering devices being the chromosomes {, each gene having an orientation given by its location on...
On the Properties of Sequences of Reversals that Sort a Signed Permutation (2002)
Anne Bergeron, Cedric Chauve, Tzvika Hartman
The sorting by reversals problem is classical in the field of whole genome comparison. In this paper, we provide experimental and theoretical evidence showing that, typically, there is a huge number...
Explicit Logspace Constructions of Weak Designs (2001)
Weak designs were defined in [RRV99a] and are used in constructions of extractors. Roughly speaking, a weak design is a collection of subsets satisfying some near-disjointness properties....