Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2009)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract—We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Curating Genetic Association Literature for Common Diseases (2009)
Elana Silver, Eran Halperin, Kord M. Kober, Badri Padhukasahasram, Nila Patil, Michelle Sommargren, ...
Papers describing genetic associations with common diseases are currently being published at a rapid rate. These new papers add to an already large body of literature which includes candidate gene...
Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir, Richard M. Karp
Population stratification can be a serious obstacle in the analysis of genomewide association studies. We propose a method for evaluating the significance of association scores in whole-genome...
Detection of molecular paths associated with insulitis and type 1 diabetes (2009)
Lindfors, Erno, Gopalacharyulu, Peddinti, Halperin, Eran, Oresic, Matej
10th International Congress of the Immunology of Diabetes Society (IDS-10). Malmö, Sweden, 17 - 20 May 2009, 52
Inference of locus-specific ancestry in closely related populations (2009)
Pasaniuc, Bogdan, Sankararaman, Sriram, Kimmel, Gad, Halperin, Eran
A characterization of the genetic variation of recently admixed populations may reveal historical population events, and is useful for the detection of single nucleotide polymorphisms (SNPs)...
Lindfors, Erno, Gopalacharyulu, Peddinti V., Halperin, Eran, Oresic, Matej
PLoS ONE Vol.4 Nr.10, e7323
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Abstract. In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V, E), the goal is to cover all the edges by picking...
On the Inference of Ancestries in Admixed Populations (2008)
Sriram Sankararaman, Gad Kimmel, Eran Halperin, Michael I. Jordan
Inference of ancestral information in recently admixed populations, in which every individual is composed of a mixed ancestry (e.g., African Americans in the US), is a challenging problem. Several...
Eran Halperin, Guy Kortsarz, Robert Krauthgamer
lower bounds for the asymmetric k-center problem
A note on phasing long genomic regions using local haplotype predictions (2008)
Eleazar Eskin, Roded Sharan, Eran Halperin
Common approaches for haplotype inference from genotype data are targeted toward phasing short genomic regions. Longer regions are often tackled in a heuristic manner, due to the high computational...
Eran Halperin, Robert Krauthgamer
We provide the first hardness result of a polylogarithmic approximation ratio for a natural NP-hard optimization problem. We show that for every fixed ɛ> 0, the Group-Steiner-Tree problem admits...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Eran Halperin, Guy Kortsarz, Robert Krauthgamer
lower bounds for the asymmetric k-center problem
An Efficient and Accurate Graph-Based Approach to Detect Population Substructure (2008)
Srinath Sridhar, Satish Rao, Eran Halperin
Abstract. Currently, large-scale projects are underway to perform whole genome disease association studies. Such studies involve the genotyping of hundreds of thousands of SNP markers. One of the...
A randomization test for controlling population stratification in (2008)
Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir, Richard M
whole-genome association studies
Gopalacharyulu, Peddinti, Velagapudi, Vidya, Lindfors, Erno, Halperin, Eran, Oresic, Matej
The 9th International Conference on Systems Biology. Göteborg, Sweden, 22 - 28 Aug. 2008, 201
My research visit to another lab - in which ways did I benefit from it (2008)
Lindfors, Erno, Halperin, Eran, Oresic, Matej
ISB 2008 Students' Spring Meeting. Lammi Biological Station, Finland, 28 - 29 May 2008
Lindfors, Erno, Gopalacharyulu, Peddinti, Arvas, Mikko, Penttilä, Merja, Halperin, Eran, Oresic, Matej
National Graduate School in Informational and Structural Biology - ISB 2008 Winter School. Ruka, Finland, 8 - 11 Dec. 2008, 14
On the inference of ancestries in admixed populations (2008)
Sankararaman, Sriram, Kimmel, Gad, Halperin, Eran, Jordan, Michael I.
Inference of ancestral information in recently admixed populations, in which every individual is composed of a mixed ancestry (e.g., African Americans in the United States), is a challenging problem....
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Abstract Reachability and distance queries via 2-hop labels (2007)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Edith Cohen, Eran Halperin, Haim Kaplan
Performance aspects of distributed caches using
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities (Extended Abstract) (2007)
Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Rajiv Gandhi , Eran Halperin , Samir Khuller , Guy Kortsarz , and Aravind Srinivasan Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported by NSF Award...
Dynamic network topology changes as result of cellular stress (2007)
Gopalacharuyly, Peddinti, Velagapudi, Vidya, Lindfors, Erno, Halperin, Eran, Oresic, Matej
15th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB) & 6th European Conference on Computational Biology (ECCB). Vienna, Austria, 21 - 25 July 2007. Abstract
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Abstract Finding the genetic factors of complex diseases such as can-cer, currently a major effort of the international community, will potentially lead to better treatment of these diseases.One of...
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major...
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major...
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2007)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at most once in...
Kirkpatrick, Bonnie, Armendariz, Carlos Santos, Karp, Richard M., Halperin, Eran
Motivation: The search for genetic variants that are linked to complex diseases such as cancer, Parkinson's;, or Alzheimer's; disease, may lead to better treatments. Since haplotypes can serve as...
A comparison of phasing algorithms for trios and unrelated individuals (2006)
Jonathan Marchini, David Cutler, Nick Patterson, Matthew Stephens, Eleazar Eskin, Eran Halperin, ...
Knowledge of haplotype phase is valuable for many analysis methods in the study of disease, population, and evolutionary genetics. Considerable research effort has been devoted to the development of...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Daphna Canetti-nisim, Eran Halperin, Stevan E. Hobfoll, Robert E. Johnson
Daphna Canetti-Nisim is an assistant professor of political science at the University of Haifa
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Using DNA pools for genotyping trios (2006)
Beckman, Kenneth B., Abel, Kenneth J., Braun, Andreas, Halperin, Eran
The genotyping of mother–father–child trios is a very useful tool in disease association studies, as trios eliminate population stratification effects and increase the accuracy of haplotype...
Using DNA pools for genotyping trios (2006)
Beckman, Kenneth B., Abel, Kenneth J., Braun, Andreas, Halperin, Eran
The genotyping of mother–father–child trios is a very useful tool in disease association studies, as trios eliminate population stratification effects and increase the accuracy of haplotype...
Using DNA pools for genotyping trios (2006)
Beckman, Kenneth B., Abel, Kenneth J., Braun, Andreas, Halperin, Eran
The genotyping of mother–father–child trios is a very useful tool in disease association studies, as trios eliminate population stratification effects and increase the accuracy of haplotype...
The common approaches for haplotype inference from genotype data are targeted toward phasing short genomic regions. Longer regions are often tackled in a heuristic manner, due to the high...
Haplofreq - estimating haplotype frequencies efficiently (2005)
A commonly used tool in disease association studies is the search for discrepancies between the haplotype distribution in the case and control populations. In order to find this discrepancy, the...
Haplofreq - estimating haplotype frequencies efficiently (2005)
A commonly used tool in disease association studies is the search for discrepancies between the haplotype distribution in the case and control populations. In order to find this discrepancy, the...
The minimum-entropy set cover problem (2005)
Abstract. We consider the minimum entropy principle for learning datagenerated by a random source and observed with random noise. In our setting we have a sequence of observations of objects drawn...
A New Algorithm for the Reconstruction of (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, ...
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
A New Algorithm for the Reconstruction of Near-Perfect Binary Phylogenetic Trees (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
Tag SNP selection in genotype data for maximizing SNP prediction accuracy (2005)
Halperin, Eran, Kimmel, Gad, Shamir, Ron
Motivation: The search for genetic regions associated with complex diseases, such as cancer or Alzheimer's disease, is an important challenge that may lead to better diagnosis and treatment. The...
Inference and analysis of haplotypes from combined genotyping studies deposited in dbSNP (2005)
Zaitlen, Noah A., Kang, Hyun Min, Feolo, Michael L., Sherry, Stephen T., Halperin, Eran, Eskin, Eleazar
In the attempt to understand human variation and the genetic basis of complex disease, a tremendous number of single nucleotide polymorphisms (SNPs) have been discovered and deposited into NCBI's...
Asymmetric k-Center is log* n-Hard to Approximate (2004)
Chuzhoy, Julia, Guha, Sudipto, Halperin, Eran, Khanna, Sanjeev, Kortsarz, Guy, Krauthgamer, Robert, ...
In the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a...
Perfect phylogeny and haplotype assignment (2004)
Eran Halperin, Richard M. Karp
This paper is concerned with the reconstruction of perfect phylogenies from binary character data with missing values, and related problems of inferring complete haplotypes from haplotypes or...
Haplotype reconstruction from genotype data using imperfect phylogeny (2004)
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
Haplotype reconstruction from genotype data using imperfect phylogeny (2004)
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
Haplotype reconstruction from genotype data using imperfect phylogeny (2004)
Halperin, Eran, Eskin, Eleazar
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
Haplotype reconstruction from genotype data using Imperfect Phylogeny (2004)
Halperin, Eran, Eskin, Eleazar
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
Haplotype reconstruction from genotype data using imperfect phylogeny (2004)
Halperin, Eran, Eskin, Eleazar
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (2003)
Gandhi, Rajiv, Halperin, Eran, Khuller, Samir, Kortsarz, Guy, Srinivasan, Aravind
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Optimally Phasing Long Genomic Regions (2003)
Using Local Haplotype, Eran Halperin, Roded Sharan
In this study we propose a novel approach for phasing genotypes over long regions, which is based on combining information from local predictions on short, overlapping regions. The phasing is done in...
Handling Long Targets and Errors in Sequencing by Hybridization (2003)
Eran Halperin, Shay Halperin, Tzvika Hartman, Ron Shamir
Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is...
Asymmetric k-center is log ∗ n-hard to approximate (2003)
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna
In the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
We present an Ω(log 2 k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Large scale reconstruction of haplotypes from genotype data (2003)
Eleazar Eskin, Eran Halperin, Richard M. Karp
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which...
Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani
Micah Adler # Department of Computer Science, University of Massachusetts, Amherst, MA 01003-4610, USA micah@cs.umass.edu Eran Halperin + Science Institute and Computer Science Division University of...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang
The natural relaxation for the Group Steiner Tree problem, as well as for its generalization, the Directed Steiner Tree problem, is a flow-based linear programming relaxation. We prove new lower...
Efficient reconstruction of haplotype structure via perfect phylogeny (2003)
Eleazar Eskin, Eran Halperin, Richard M. Karp
Each person’s genome contains two copies of each chromosome, one inherited from the father and the other from the mother. A person’s genotype specifies the pair of bases at each site, but does...
Integrality ratio for group steiner trees and directed steiner trees (2003)
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan
We present an Ω(log 2 k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs...
Reachability and Distance Queries via 2-hop Labels (2002)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
1 Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Improved approximation algorithms for the partial vertex cover problem (2002)
Abstract. The partial vertex cover problem is a generalization of the vertex cover problem: given an undirected graph G = (V; E) and an integer k, we wish to choose a minimum number of vertices such...
Coloring k-colorable graphs using smaller palettes (2001)
Eran Halperin, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: ffl A 3-colorable graph on n vertices with maximum degree \Delta can be colored, in polynomial time, using O((\Delta log \Delta) 1=3 \Delta log n)...
Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem (2001)
We describe several combinatorial algorithms for the maximum directed cut problem. Among our results is a simple linear time 9/20-approximation algorithm for the problem, and a somewhat slower...
Coloring k-Colorable Graphs Using Smaller Palettes (2001)
Eran Halperin, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: A 3-colorable graph on n vertices with maximum degree can be colored, in polynomial time, using O(( log ) log n) colors. This slightly improves an O(( )...
MAX CUT in cubic graphs (2001)
Eran Halperin, Dror Livnat, Uri Zwick
We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least...
We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX n/2-BISECTION -- partition...
Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs (1999)
Karloff and Zwick obtained recently an optimal 7=8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7=8-approximation algorithm for MAX SAT,...
Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs (1999)
. Karloff and Zwick obtained recently an optimal 7=8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7=8-approximation algorithm for MAX...
FramePlus: aligning DNA to protein sequences (1999)
Halperin, Eran, Faigler, Simchon, Gill-More, Raveh
Motivation: Automated annotation of Expressed Sequence Tags (ESTs) is becoming increasingly important as EST databases continue to grow rapidly. A common approach to annotation is to align the gene...
Bipartite subgraphs of integer weighted graphs (1998)
For every integer p> 0 let f(p) be the minimum possible value of the maximum weight of a cut in an integer weighted graph with total weight p. It is shown that for every large n and every m <...
Eran Halperin, Ami Pedahzur, Daphna Canetti-Nisim
We aspired to reexamine the well-established assumption according to which low socioeconomic status, as a comprehensive concept, leads to prejudice and hostile attitudes toward minorities. Hence, we...
Skibola, Christine F., Bracci, Paige M., Halperin, Eran, Nieters, Alexandra, Hubbard, Alan, Paynter, Randi A., ...
On the inference of ancestries in admixed populations
Sankararaman, Sriram, Kimmel, Gad, Halperin, Eran, Jordan, Michael I.
Inference of ancestral information in recently admixed populations, in which every individual is composed of a mixed ancestry (e.g., African Americans in the United States), is a challenging problem....
Estimating Local Ancestry in Admixed Populations
Sankararaman, Sriram, Sridhar, Srinath, Kimmel, Gad, Halperin, Eran
Large-scale genotyping of SNPs has shown a great promise in identifying markers that could be linked to diseases. One of the major obstacles involved in performing these studies is that the...
Association Mapping and Significance Estimation via the Coalescent
Kimmel, Gad, Karp, Richard M., Jordan, Michael I., Halperin, Eran
The central questions asked in whole-genome association studies are how to locate associated regions in the genome and how to estimate the significance of these findings. Researchers usually do this...
Inference of locus-specific ancestry in closely related populations
Paşaniuc, Bogdan, Sankararaman, Sriram, Kimmel, Gad, Halperin, Eran
A characterization of the genetic variation of recently admixed populations may reveal historical population events, and is useful for the detection of single nucleotide polymorphisms (SNPs)...
Lindfors, Erno, Gopalacharyulu, Peddinti V., Halperin, Eran, Orešič, Matej
Recent clinical evidence suggests important role of lipid and amino acid metabolism in early pre-autoimmune stages of type 1 diabetes pathogenesis. We study the molecular paths associated with the...