Algorithmic approaches for the single individual haplotyping problem
RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 2, pp. 331-340.

Since its introduction in 2001, the Single Individual Haplotyping problem has received an ever-increasing attention from the scientific community. In this paper we survey, in the form of an annotated bibliography, the developments in the study of the problem from its origin until our days.

Received:
Accepted:
DOI: 10.1051/ro/2015037
Classification: 90B, 92B
Keywords: Operation research and management science, mathematical biology in general
Lancia, Giuseppe 1

1 DIMI, University of Udine, Via delle Scienze 206, 33100 Udine, Italy.
@article{RO_2016__50_2_331_0,
     author = {Lancia, Giuseppe},
     title = {Algorithmic approaches for the single individual haplotyping problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {331--340},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     doi = {10.1051/ro/2015037},
     mrnumber = {3479873},
     zbl = {1337.92143},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2015037/}
}
TY  - JOUR
AU  - Lancia, Giuseppe
TI  - Algorithmic approaches for the single individual haplotyping problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 331
EP  - 340
VL  - 50
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2015037/
DO  - 10.1051/ro/2015037
LA  - en
ID  - RO_2016__50_2_331_0
ER  - 
%0 Journal Article
%A Lancia, Giuseppe
%T Algorithmic approaches for the single individual haplotyping problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 331-340
%V 50
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2015037/
%R 10.1051/ro/2015037
%G en
%F RO_2016__50_2_331_0
Lancia, Giuseppe. Algorithmic approaches for the single individual haplotyping problem. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 2, pp. 331-340. doi : 10.1051/ro/2015037. http://archive.numdam.org/articles/10.1051/ro/2015037/

D. Aguiar and S. Istrail, HapCompass: A fast cycle basis algorithm for accurate haplotype assembly of sequence data. J. Comput. Biol. 19 (2012) 577–590. | DOI | MR

D. Aguiar and S. Istrail, Haplotype assembly in polyploid genomes and identical by descent shared tracts. Bioinformatics 29 (2013) 352–360. | DOI

V. Bafna, S. Istrail, G. Lancia and R. Rizzi, Polynomial and APX-hard cases of the individual haplotyping problem. Theoret. Comput. Sci. 335 (2005) 109–125. | DOI | MR | Zbl

V. Bansal and V. Bafna, HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics 24 (2008) i153–i159. | DOI

S. Bayzid, M. Alam, A. Mueen and S. Rahman, A fast and accurate algorithm for diploid individual haplotype reconstruction. J. Bioinform. Comput. Biol. 11 (2013) 1–12.

S. Bayzid, M. Alam, A. Mueen and S. Rahman, Hmec: A heuristic algorithm for individual haplotyping with minimum error correction. ISRN Bioinformatics 2013 (2013) 1–10. | DOI

K. Booth and G. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using pq-tree algorithms. J. Comput. System Sci. 13 (1976) 335–379. | DOI | MR | Zbl

V. Bansal, A. Halpern, N. Axelrod and V. Bafna, An MCMC algorithm for haplotype assembly from whole-genome sequence data. Genome Res. 18 (2008) 1336–1346. | DOI

Z. Chen, B. Fu, R. Schweller, B. Yang, Z. Zhao and B. Zhu, Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments. J. Comput. Biolo. 15 (2008) 535–546. | DOI | MR

Z. Chen, F. Deng and L. Wang, Exact algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 29 (2013) 1938–1945. | DOI

R. Cilibrasi, L. V. Iersel, S. Kelk and J. Tromp, On the complexity of several haplotyping problems. Proc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Vol. 3692 of Lect. Notes Comput. Sci. Springer (2005) 128–139. | MR

I.H. Consortium, The international hapmap project. Nature 426 (2003) 789–796. | DOI

F.S. Collins, M. Morgan and A. Patrinos, The human genome project: Lessons from large-scale biology. Science 300 (2003) 286–290. | DOI

F. Deng, W. Cui and L. Wang, A highy accurate heuristic algorithm for the haplotype assembly problem. BMC Genomics 14 (2013) 1–10. | DOI

J. Douglas, M. Boehnke, E. Gillanders, J. Trent and S. Gruber, Experimentally-derived haplotypes substantially increase the efficiency of linkage disequilibrium studies. Nature Genetics 28 (2001) 361–364. | DOI

J. Duitama, T. Huebsch, G. McEwen, E. Suk and M. Hoehe, Refhap: a reliable and fast algorithm for single individual haplotyping, In Proc. of the 1st ACM International conference on Bioinformatics and Computational Biology, DMTCS’03. ACM. New York (2010) 160–169.

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Edited by W.H. Freeman (1979). | MR | Zbl

L. Genovese, F. Geraci and M. Pellegrini, Speedhap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage. IEEE/ACM Trans Comput Biol Bioinform. 5 (2008) 492–502. | DOI

F. Geraci, A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem. Bioinformatics 26 (2010) 2217–2225. | DOI

F. Geraci and M. Pellegrini, Rehap: an integrated system for the haplotype assembly problem from shotgun sequencing data. In BIOINFORMATICS 2010 − Proc. of the First International Conference on Bioinformatics, edited by A.L. N. Fred, J. Filipe and H. Gamboa. INSTICC Press (2010) 15–25.

H. Greenberg, W. Hart and G. Lancia, Opportunities for combinatorial optimization in computational biology. INFORMS J. Comput. 16 (2004) 1–22. | DOI | MR | Zbl

D. Gusfield and S.H. Orzack, Haplotype inference. In Handbook of Computational Molecular Biology. Champman and Hall/CRC-press (2005) 1–28.

D. He, A. Choi, K. Pipatsrisawat, A. Darwiche and E. Eskin, Optimal algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 26 (2010) i83–i190.

M. Kargar, H. Poormohammadi, L. Pirhaji, M. Sadeghi, H. Pezeshk and C. Eslahchi, Enhanced evolutionary and heuristic algorithms for haplotype reconstruction problem using minimum error correction model. MATCH Commun. Math. Comput. Chem. 62 (2009) 261–274. | MR | Zbl

G. Lancia, V. Bafna, S. Istrail, R. Lippert and R. Schwartz, SNPs problems, complexity and algorithms. In Proc. of the Annual European Symposium on Algorithms (ESA). Vol. 2161 of Lect. Notes Comput. Sci. Springer (2001) 182–193. | MR | Zbl

S. Levy, et al. The diploid genome sequence of an individual human. PLoS Biol. 5 (2007) e254. | DOI

L. Li, J. Kim and M. Waterman, Haplotype reconstruction from SNP alignment. J. Comput. Biology 11 (2004) 507–518.

R. Lippert, R. Schwartz, G. Lancia and S. Istrail, Algorithmic strategies for the SNPs haplotype assembly problem. Briefings in Bioinformatics 3 (2002) 23–31. | DOI

A. Panconesi and M. Sozio, Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. In Proc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Vol. 3240 of Algorithms in Bioinformatics. Springer (2004) 266–277.

R. Rizzi, V. Bafna, S. Istrail and G. Lancia, Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem, in Proc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Edited by R. Guigo and D. Gusfield. Vol. 2452 of Lect. Notes Comput. Sci. Springer (2002) 29–43. | Zbl

J. Venter, et al.. The sequence of the human genome. Science 291 (2001) 1304–1351. | DOI

R. Wang, L. Wu, Z. Li and X. Zhang, Haplotype reconstruction from SNP fragments by minimum error correction. Bioinformatics 21 (2005) 2456–2462. | DOI

R. Wang, L. Wu, X. Zhang and L. Chen, A markov chain model for haplotype assembly from SNP fragments. Genome Inform 17 (2006) 162–171.

J. Wu, J. Wang and J. Chen, A heuristic algorithm for haplotype reconstruction from aligned weighted SNP fragments. Int. J. Bioinform. Res. Appl. 9 (2013) 13–24. | DOI

M. Xie and J. Wang, An improved (and practical) parametrized algorithm for the individual haplotyping problem MFR with mate pairs. Algorithmica 52 (2008) 250–266. | DOI | MR | Zbl

M. Xie, J. Wang and J. Chen, A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors. Bioinformatics 24 (2008) i105–i113. | DOI

M. Xie, J. Wang and T. Jiang, A fast and accurate algorithm for single individual haplotyping. BMC Systems Biology 6 (2012) 1–10.

Y. Zhao, L. Wu, J. Zhang, R. Wang and X. Zhang, Haplotype assembly from aligned weighted SNP fragments. Comput Biol. Chem. 29 (2005) 281–287. | DOI | Zbl

X. Zhang, R. Wang, A. Wu and W. Zhang, Minimum conflict individual haplotyping from SNP fragments and related genotype. Evolutionary Bioinformatics Online 2 (2006) 271–280.

Cited by Sources: