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.
Accepté le :
DOI : 10.1051/ro/2015037
Mots-clés : Operation research and management science, mathematical biology in general
@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, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 331-340. doi : 10.1051/ro/2015037. http://archive.numdam.org/articles/10.1051/ro/2015037/
and , HapCompass: A fast cycle basis algorithm for accurate haplotype assembly of sequence data. J. Comput. Biol. 19 (2012) 577–590. | DOI | MR
and , Haplotype assembly in polyploid genomes and identical by descent shared tracts. Bioinformatics 29 (2013) 352–360. | DOI
, , and , Polynomial and APX-hard cases of the individual haplotyping problem. Theoret. Comput. Sci. 335 (2005) 109–125. | DOI | MR | Zbl
and , HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics 24 (2008) i153–i159. | DOI
, , and , A fast and accurate algorithm for diploid individual haplotype reconstruction. J. Bioinform. Comput. Biol. 11 (2013) 1–12.
, , and , Hmec: A heuristic algorithm for individual haplotyping with minimum error correction. ISRN Bioinformatics 2013 (2013) 1–10. | DOI
and , 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
, , and , An MCMC algorithm for haplotype assembly from whole-genome sequence data. Genome Res. 18 (2008) 1336–1346. | DOI
, , , , and , Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments. J. Comput. Biolo. 15 (2008) 535–546. | DOI | MR
, and , 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
, The international hapmap project. Nature 426 (2003) 789–796. | DOI
, and , The human genome project: Lessons from large-scale biology. Science 300 (2003) 286–290. | DOI
, and , A highy accurate heuristic algorithm for the haplotype assembly problem. BMC Genomics 14 (2013) 1–10. | DOI
, , , and , 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
, and , 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
, 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.
, and , 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.
, , , and , Optimal algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 26 (2010) i83–i190.
, , , , and , 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
, et al. The diploid genome sequence of an individual human. PLoS Biol. 5 (2007) e254. | DOI
, and , Haplotype reconstruction from SNP alignment. J. Comput. Biology 11 (2004) 507–518.
, , and , 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
, et al.. The sequence of the human genome. Science 291 (2001) 1304–1351. | DOI
, , and , Haplotype reconstruction from SNP fragments by minimum error correction. Bioinformatics 21 (2005) 2456–2462. | DOI
, , and , A markov chain model for haplotype assembly from SNP fragments. Genome Inform 17 (2006) 162–171.
, and , A heuristic algorithm for haplotype reconstruction from aligned weighted SNP fragments. Int. J. Bioinform. Res. Appl. 9 (2013) 13–24. | DOI
and , An improved (and practical) parametrized algorithm for the individual haplotyping problem MFR with mate pairs. Algorithmica 52 (2008) 250–266. | DOI | MR | Zbl
, and , 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
, and , A fast and accurate algorithm for single individual haplotyping. BMC Systems Biology 6 (2012) 1–10.
, , , and , Haplotype assembly from aligned weighted SNP fragments. Comput Biol. Chem. 29 (2005) 281–287. | DOI | Zbl
, , and , Minimum conflict individual haplotyping from SNP fragments and related genotype. Evolutionary Bioinformatics Online 2 (2006) 271–280.
Cité par Sources :
