Publication_List

Publications

Choose papers by subject:

Recent Publications.
Projects, Software and Patents.
Human Variation.
Biological Sequences.
Algorithms.
Complexity and Lower Bounds.

Overview of my research.

News:

Projects, Software and Patents

  • LAMP: Estimating Locus Specific Ancestry
  • HAP: Haplotype analysis tool.
  • WHAP: Weighted Haplotype Association Server.
  • HaploPool: Estimating Haplotype Frequencies from genotypes or from DNA pools.
  • GEVALT: Selecting the most predicting tag SNPs.
  • TRIPLETS: Discover Population Substructure
  • SCIMP: Scan for Imperfect Phylogeneis
  • HAPLOFREQ: Haplotype frequency estimation in a population.
  • TrioPhase: Genotyping trios using DNA pools.
  • EMBED: Embedding proteins into Euclidean space (for the comparison of protein databases).
  • United States Patent 6,625,545: Method and apparatus for mRNA assembly.

Recent Publications

  1. Skibola CF, Bracci PM, Halperin E, Nieters A, Hubbard A, Paynter RA, Skibola DR, Agana L, Becker N, Tressler P, Forrest MS, Sankararaman S, Conde L, Holly EA, Smith MT,
    Polymorphisms in the estrogen receptor 1 and vitamin C and matrix metalloproteinase gene families are associated with susceptibility to lymphoma, PLoS ONE, 3(7), 2008.

  2. Sriram Sankararaman, Gad Kimmel, Eran Halperin, and Michael I. Jordan,
    On the inference of ancestries in admixed populations, Genome Research, 18:668-675, 2008 (special issue of RECOMB, 2008).

  3. Sriram Sankararaman, Srinath Sridhar, Gad Kimmel, and Eran Halperin,
    LAMP: Local Ancestry in adMixed Populations, The American Journal of Human Genetics, Volume 82, Issue 2, 290-303, 2008. [AJHG]

  4. Bonnie Kirkpatrick, Carlos Santos Armendariz, Richard M Karp, and Eran Halperin
    HAPLOPOOL: Improving Haplotype Frequency Estimation through DNA Pools and Phylogenetic Modeling, Bioinformatics, 23(22): 3048-3055 (2007).[Bioinformatics].

  5. Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir and Richard M. Karp
    A randomization test for controlling population stratification in whole-genome association studies, The American Jounal of Human Genetics, 81:895-905, 2007. [AJHG].

  6. Noah Zaitlen, Hyun Min Kang, Eleazar Eskin, Eran Halperin
    Leveraging the HapMap Correlation Structure in Association Studies, The American Jounal of Human Genetics, 80:683-691, 2007. [AJHG]

  7. Srinath Sridhar, Satish Rao, Eran Halperin
    An Efficient and Accurate Graph-based Approach to Detect Population Substructure, appeared in RECOMB, 2007. [pdf]

  8. Srinath Sridhar, Kedar Dhamdhere, Guy E. Blleloch, Eran Halperin, R. Ravi, and Russell Schwartz
    Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice, IEEE/ACM Trans. Comput. Biology Bioinform. (TCBB) 4(4):561-571 (2007).

  9. Kenneth B. Beckman, Kenneth A. Abel, Andreas Braun and Eran Halperin
    Using DNA Pools for Genotyping Trios, Nucleic Acids Research, 2006; doi: 10.1093/nar/gkl700. [Nucleic Acids Research].

  10. Kamalika Chaudhuri, Eran Halperin, Satish Rao and Shuheng Zhou
    A Rigorous Analysis of Population Stratification with Limited Data, ACM-SIAM Symposium on Discrete Algorithms ( SODA ), 2007. [pdf]

  11. Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, and Srinath Sridhar
    Fixed Parameter tractability of Binary Near-Perfect Phylogenetic Tree Reconstructions, ICALP, 2006. [pdf]

  12. Jonathan Marchini, David Cutler, Nick Patterson, Matthew Stephens, Eleazar Eskin, Eran Halperin, Shin Lin, Steve Qin, Goncalo Abecassis, Heather Munro and Peter Donnelly
    A comparison of phasing algorithms for trios and unrelated individuals, American journal of Human Genetics, 78 437-450, 2006.

  13. Eran Halperin and Elad Hazan
    HAPLOFREQ - Estimating Haplotype Frequencies Efficiently, RECOMB, 2005. Also in a special issue of Journal of Computational Biology,March 2006, Vol. 13, No. 2: 481-500. [pdf]

  14. Eleazar Eskin, Roded Sharan and Eran Halperin
    Optimally Phasing Long Genomic Regions using Local Haplotype Predictions, JBCB ,4, pp. 639-647, 2006. [pdf]

Human Variation

  • Skibola CF, Bracci PM, Halperin E, Nieters A, Hubbard A, Paynter RA, Skibola DR, Agana L, Becker N, Tressler P, Forrest MS, Sankararaman S, Conde L, Holly EA, Smith MT,
    Polymorphisms in the estrogen receptor 1 and vitamin C and matrix metalloproteinase gene families are associated with susceptibility to lymphoma, PLoS ONE, 3(7), 2008.

  • Sriram Sankararaman, Gad Kimmel, Eran Halperin, and Michael I. Jordan,
    On the inference of ancestries in admixed populations, Genome Research, 18:668-675, 2008 (special issue of RECOMB, 2008).

  • Sriram Sankararaman, Srinath Sridhar, Gad Kimmel, and Eran Halperin,
    LAMP: Local Ancestry in adMixed Populations, The American Journal of Human Genetics, Volume 82, Issue 2, 290-303, 2008. [AJHG]

  • Bonnie Kirkpatrick, Carlos Santos Armendariz, Richard M Karp, and Eran Halperin
    HAPLOPOOL: Improving Haplotype Frequency Estimation through DNA Pools and Phylogenetic Modeling, Bioinformatics, 23(22): 3048-3055 (2007).[Bioinformatics].

  • Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir and Richard M. Karp
    A randomization test for controlling population stratification in whole-genome association studies, The American Jounal of Human Genetics, 81:895-905, 2007. [AJHG].

  • Noah Zaitlen, Hyun Min Kang, Eleazar Eskin, Eran Halperin
    Leveraging the HapMap Correlation Structure in Association Studies The American Jounal of Human Genetics, 80:683-691, 2007. [AJHG]

  • Srinath Sridhar, Satish Rao, Eran Halperin
    An Efficient and Accurate Graph-based Approach to Detect Population Substructure, appeared in RECOMB, 2007. [pdf]

  • Srinath Sridhar, Kedar Dhamdhere, Guy E. Blleloch, Eran Halperin, R. Ravi, and Russell Schwartz
    Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice, IEEE/ACM Trans. Comput. Biology Bioinform. (TCBB) 4(4):561-571 (2007).

  • Kenneth B. Beckman, Kenneth A. Abel, Andreas Braun and Eran Halperin
    Using DNA Pools for Genotyping Trios, Nucleic Acids Research, 2006; doi: 10.1093/nar/gkl700. [Nucleic Acids Research].

  • Kamalika Chaudhuri, Eran Halperin, Satish Rao and Shuheng Zhou
    A Rigorous Analysis of Population Stratification with Limited Data, ACM-SIAM Symposium on Discrete Algorithms ( SODA ), 2007. [pdf]

  • Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, and Srinath Sridhar
    Fixed Parameter tractability of Binary Near-Perfect Phylogenetic Tree Reconstructions, ICALP, 2006. [pdf]

  • Jonathan Marchini, David Cutler, Nick Patterson, Matthew Stephens, Eleazar Eskin, Eran Halperin, Shin Lin, Steve Qin, Goncalo Abecassis, Heather Munro and Peter Donnelly
    A comparison of phasing algorithms for trios and unrelated individuals, American journal of Human Genetics, 78 437-450, 2006.

  • Noah A. Zaitlen, Hyun Min Kang, Michael L. Feolo, Stephen T. Sherry, Eran Halperin, and Eleazar Eskin
    Inference and analysis of haplotypes from combined genotyping studies deposited in dbSNP, Genome Research, 2005, 15:1594-1600. [Genome Research].

  • David A. Hinds, Laura L. Stuve, Geoffrey B. Nilsen, Eran Halperin, Eleazar Eskin, Dennis G. Ballinger, Kelly A. Frazer, David R. Cox
    Whole-Genome Patterns of Common DNA Variation in Three Human Populations, Science, 18 February 2005: 1072-1079. [Science Website].

  • Eran Halperin, Gad Kimmel, Ron Shamir
    Tag SNP Selection in Genotype Data for Maximizing SNP Prediction Accuracy, ISMB (Supplement of Bioinformatics), 2005: 195-203. [pdf]

  • Eran Halperin and Elad Hazan
    HAPLOFREQ - Estimating Haplotype Frequencies Efficiently, RECOMB, 2005. Also in a special issue of Journal of Computational Biology,March 2006, Vol. 13, No. 2: 481-500. [pdf]

  • Eran Halperin and Richard M. Karp
    The Minimum-Entropy Set Cover Problem, ICALP 2004, 733--744. [pdf]

  • Eran Halperin and Richard M. Karp
    Perfect Phylogeny and Haplotype Assignment, RECOMB , 2004. [pdf]

  • Eleazar Eskin, Roded Sharan and Eran Halperin
    Optimally Phasing Long Genomic Regions using Local Haplotype Predictions, JBCB ,4, pp. 639-647, 2006. [pdf]

  • Eleazar Eskin, Eran Halperin and Richard M. Karp
    Large Scale Reconstruction of Haplotypes from Genotype Data, RECOMB , 2003, 104--113.

  • Eleazar Eskin, Eran Halperin and Richard M. Karp
    Efficient Reconstruction of Haplotype Structure via Perfect Phylogeny, JBCB , 1 (1) 1-20, 2003. [pdf]

  • Eran Halperin and Eleazar Eskin
    Haplotype Reconstruction from Genotype Data using Imperfect Phylogeny, Bioinformatics 20(12): 1842-1849 (2004). [pdf]

Biological Sequences

  • Eran Halperin, Jeremy Buhler,Richard Karp, Robert Krauthgamer and Ben Westover
    Detecting Protein Sequences Via Metric Embeddings, ISMB 2003, 122-199. [pdf]

  • Eran Halperin, Shay Halperin, Tzvika Hartman and Ron Shamir
    Handling long targets and errors in sequencing by hybridization, RECOMB , 2002, 176-185. Also in a special issue of Jour. Comp. Biology . [pdf]

  • Eran Halperin, Simchon Faigler and Raveh Gill-More
    FramePlus: A sensitive algorithm for aligning DNA to protein sequences, Bioinformatics 15 (11):867-873 1999. [pdf]

  • Mor Amitai, Raveh Gill-More, Eran Halperin, Avner Magen, Sarah Pollock. >United States Patent 6,625,545: Method and apparatus for mRNA assembly. (1998)

Algorithms

  • Kamalika Chaudhuri, Eran Halperin, Satish Rao and Shuheng Zhou
    A Rigorous Analysis of Population Stratification with Limited Data, ACM-SIAM Symposium on Discrete Algorithms ( SODA ), 2007. [pdf]

  • Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, and Srinath Sridhar
    Fixed Parameter tractability of Binary Near-Perfect Phylogenetic Tree Reconstructions, ICALP, 2006. [pdf]

  • Eran Halperin and Richard M. Karp
    The Minimum-Entropy Set Cover Problem, ICALP 2004, 733--744. [ps]

  • Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz and Aravind Srinivasan An Improved Approximation Algorithm for Vertex Cover with Hard Capacities, ICALP , 164--175, (2003). [ps]

  • Micah Adler, Eran Halperin, Richard Karp and Vijay Vazirani
    A stochastic process on the hypercube with applications to peer to peer networks, STOC , 2003, 575--584. [ps]

  • Eran Halperin and Aravind Srinivasan
    Improved Approximation Algorithms for the Partial Vertex Cover Problem, APPROX , 2002, 161-175. [ps]

  • Eran Halperin, Dror Livnat and Uri Zwick
    MAX CUT in cubic graphs, SODA , 2002, 506-513. [pdf]

  • Edith Cohen, Eran Halperin, Haim Kaplan and Uri Zwick
    Reachability and distance queries via 2-hop labels, SICOMP , 32 (5):1338-1355 (2003). Also, in SODA , 2002, 937--946. [pdf]

  • Edith Cohen, Eran Halperin and Haim Kaplan
    Performance aspects of distributed caches using TTL-based consistency, a special issue of Theor. Comput. Sci. 331(1): 73-96 (2005). Also, in ICALP , 2001, 744--756. [ps]

  • Eran Halperin and Uri Zwick
    A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, a special issue of Random Structures and Algorithms ( RSA ), 20(3):382-402 (2002). Also, IPCO , 2001, 202-217. [ps]

  • Eran Halperin and Uri Zwick
    Combinatorial approximation algorithms for the maximum directed cut problem, SODA , 2001, 1-7. [ps]

  • Eran Halperin, Ram Nathaniel and Uri Zwick
    Coloring k-colorable graphs using smaller palettes. Journal of Algorithms , 45(1): 72-90 (2002). Also, in SODA , 2001, 319-326. [ps]

  • Eran Halperin
    Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, SICOMP , 31, 1608-1623, (2002). Also, in SODA , 2000, 329-337. [ps]

  • Eran Halperin and Uri Zwick
    Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs, Journal of Algorithms , 40, 184-211 (2001). Also, in IPCO , 1999, 202-217. [ps]

Complexity and Lower Bounds

  • Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan and Nan Wang
    Integrality ratio for Group Steiner Trees and Directed Steiner Trees, SIAM Journal on Computing , Vol. 36, 1494-1511, 2007. A preliminary version appeared in SODA, 2003. [ps]

  • Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer and Seffi Naor
    Tight lower bounds for the asymmetric k-center problem, Journal of the ACM, 52(4):538-551, 2005. Also, in STOC , 2004. [ps].

  • Eran Halperin and Robert Krauthgamer
    Polylogarithmic Inapproximability, STOC , 2003, 585--594. [ps]

Combinatorics

  • Noga Alon and Eran Halperin
    Bipartite subgraphs of integer weighted graphs, Discrete Mathematics 181, (1998), 19-29.