×
Lancia, Giuseppe

Algorithmic approaches for the single individual haplotyping problem. (English) Zbl 1337.92143

RAIRO, Oper. Res. 50, No. 2, 331-340 (2016).
Summary: 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.

Cited in 1 Document

MSC:

92D10 Genetics and epigenetics
92D20 Protein sequences, DNA sequences
92-04 Software, source code, etc. for problems pertaining to biology

Keywords:

haplotyping problem; minimum fragment

Software:

ReHap; SpeedHap; ReFHap; HapCUT
Cite Review PDF
Full Text: DOI Link

References:

[1] 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:10.1089/cmb.2012.0084
[2] D. Aguiar and S. Istrail, Haplotype assembly in polyploid genomes and identical by descent shared tracts. Bioinformatics29 (2013) 352-360. · doi:10.1093/bioinformatics/btt213
[3] 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. · Zbl 1080.68037 · doi:10.1016/j.tcs.2004.12.017
[4] V. Bansal and V. Bafna, HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics24 (2008) i153-i159. · doi:10.1093/bioinformatics/btn298
[5] 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.
[6] S. Bayzid, M. Alam, A. Mueen and S. Rahman, Hmec: A heuristic algorithm for individual haplotyping with minimum error correction. ISRN Bioinformatics2013 (2013) 1-10. · doi:10.1155/2013/291741
[7] 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. · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[8] 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:10.1101/gr.077065.108
[9] 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:10.1089/cmb.2008.0003
[10] Z. Chen, F. Deng and L. Wang, Exact algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics29 (2013) 1938-1945. · doi:10.1093/bioinformatics/btt349
[11] 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. · Zbl 1131.68049
[12] I.H. Consortium, The international hapmap project. Nature426 (2003) 789-796. · doi:10.1038/nature02168
[13] F.S. Collins, M. Morgan and A. Patrinos, The human genome project: Lessons from large-scale biology. Science300 (2003) 286-290. · doi:10.1126/science.1084564
[14] F. Deng, W. Cui and L. Wang, A highy accurate heuristic algorithm for the haplotype assembly problem. BMC Genomics14 (2013) 1-10. · doi:10.1186/1471-2164-14-593
[15] J. Douglas, M. Boehnke, E. Gillanders, J. Trent and S. Gruber, Experimentally-derived haplotypes substantially increase the efficiency of linkage disequilibrium studies. Nature Genetics28 (2001) 361-364. · doi:10.1038/ng582
[16] 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.
[17] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Edited by W.H. Freeman (1979). · Zbl 0411.68039
[18] 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:10.1109/TCBB.2008.67
[19] F. Geraci, A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem. Bioinformatics26 (2010) 2217-2225. · doi:10.1093/bioinformatics/btq411
[20] 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.
[21] H. Greenberg, W. Hart and G. Lancia, Opportunities for combinatorial optimization in computational biology. INFORMS J. Comput.16 (2004) 1-22. · Zbl 1239.90003 · doi:10.1287/ijoc.16.1.1.27671
[22] D. Gusfield and S.H. Orzack, Haplotype inference. In Handbook of Computational Molecular Biology. Champman and Hall/CRC-press (2005) 1-28.
[23] D. He, A. Choi, K. Pipatsrisawat, A. Darwiche and E. Eskin, Optimal algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics26 (2010) i83-i190.
[24] 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. · Zbl 1417.92107
[25] 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. · Zbl 1016.92023
[26] S. Levy, et al. The diploid genome sequence of an individual human. PLoS Biol.5 (2007) e254. · doi:10.1371/journal.pbio.0050254
[27] L. Li, J. Kim and M. Waterman, Haplotype reconstruction from SNP alignment. J. Comput. Biology11 (2004) 507-518.
[28] R. Lippert, R. Schwartz, G. Lancia and S. Istrail, Algorithmic strategies for the SNPs haplotype assembly problem. Briefings in Bioinformatics3 (2002) 23-31. · doi:10.1093/bib/3.1.23
[29] 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.
[30] 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 1016.68685
[31] J. Venter, et al.. The sequence of the human genome. Science291 (2001) 1304-1351. · doi:10.1126/science.1058040
[32] R. Wang, L. Wu, Z. Li and X. Zhang, Haplotype reconstruction from SNP fragments by minimum error correction. Bioinformatics21 (2005) 2456-2462. · doi:10.1093/bioinformatics/bti352
[33] R. Wang, L. Wu, X. Zhang and L. Chen, A markov chain model for haplotype assembly from SNP fragments. Genome Inform17 (2006) 162-171.
[34] 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:10.1504/IJBRA.2013.050743
[35] M. Xie and J. Wang, An improved (and practical) parametrized algorithm for the individual haplotyping problem MFR with mate pairs. Algorithmica52 (2008) 250-266. · Zbl 1173.68834 · doi:10.1007/s00453-007-9150-2
[36] 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. Bioinformatics24 (2008) i105-i113. · doi:10.1093/bioinformatics/btn147
[37] M. Xie, J. Wang and T. Jiang, A fast and accurate algorithm for single individual haplotyping. BMC Systems Biology6 (2012) 1-10. · doi:10.1186/1752-0509-6-1
[38] 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. · Zbl 1102.92031 · doi:10.1016/j.compbiolchem.2005.05.001
[39] X. Zhang, R. Wang, A. Wu and W. Zhang, Minimum conflict individual haplotyping from SNP fragments and related genotype. Evolutionary Bioinformatics Online2 (2006) 271-280.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.