JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (4): 9-14.doi: 10.6040/j.issn.1672-3961.1.2016.229

Previous Articles     Next Articles

An improved cycle basis algorithm for haplotyping a diploid individual

WU Huimin1, WU Jingli1,2,3   

  1. 1. College of Computer Science and Information Technology, Guangxi Normal University, Guilin 541004, Guangxi, China;
    2. Guangxi Key Lab of Multi-source Information Mining &
    Security, Guangxi Normal University, Guilin 541004, Guangxi, China;
    3. Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing, Guilin 541004, Guangxi, China
  • Received:2016-03-01 Online:2016-08-20 Published:2016-03-01

PDF (PC)

756

Abstract: HapCompass is an effective heuristic algorithm for solving the minimum weighted edge removal(MWER)model. The HapCompass algorithm eliminated conflicting cycle basis by deleting the edge with the minimum absolute value of weight. When there were several edges whose absolute values of weights were equal to the minimum one, HapCompass chose the deleted one randomly, which led to produce uncertain solutions and decrease the reconstruction effect. Aiming at this problem, algorithm IHapCompass was proposed. It improved the rules of deleting edges to limit the random value effectively. IHapCompass took advantage of the relativity between the difference of fragment number of(00)/(11)and that of(01)/(10)and the total fragment number to ascertain the deleted edge. It made use of the probability of 0/1 in haplotypes to determine the SNP value for an isolated vertex, which ascertained the value of an isolated vertex. Experiments were implemented by using the real haplotypes. The results showed that under different parameter settings, the IHapCompass algorithm can obtain higher reconstruction rate than the HapCompass, the DGS and the Fast Hare algorithm, and has high efficiency. The IHapCompass algorithm could provide a reference for the study on reconstructing single diploid individual haplotypes.

Key words: reconstruction, graph, the minimum weighted edge removal, sequence analysis, haplotype

CLC Number: 

  • TP301.6
[1] LANCIA G, BAFNA V, ISTRAIL S, et al. SNPs problems, complexity, and algorithms[C] // Proceedings of ESA-01. Aarhusv Denmark: Springer Press, 2001:182-193.
[2] LIPPERT R, SCHWARTZ R, LANCIA G, et al. Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem[J]. Briefings in Bioinformatics, 2002, 3(1):23-31.
[3] SCHWARTZ R. Theory and algorithms for the haplotype assembly problem[J]. Communications in Information & Systems, 2010, 10(1):23-38.
[4] GERACI F. A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem[J]. Bioinformatics, 2010, 26(18):2217-2225.
[5] AGUIAR D, ISTRAIL S. HapCompass: a fast cycle basis algorithm for accurate haplotype assembly of sequence data[J]. Journal of Computational Biology, 2012, 19(6):577-590.
[6] XIE Minzhu, WANG Jianxin, CHEN Xin. LGH: a fast and accurate algorithm for single individual haplotyping based on a two-locus linkage graph[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015, 12(6):1255-1266.
[7] RIZZI R, BAFNA V, ISTRAIL S, et al. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem[C] //Proceedings of WABI-02. Rome, Italy: Springer Press, 2002:29-43.
[8] BAFNA V, ISTRAIL S, LANCIA G, et al. Polynomial and APX-hard cases of the individual haplotyping problem[J]. Theoretical Computer Science, 2005, 335(1):109-125.
[9] XIE Minzhu, CHEN Jian'er, WANG Jianxin. Research on parameterized algorithms of the individual haplotyping problem[J]. Journal of Bioinformatics and Computational Biology, 2007, 5(3):795-816.
[10] CILIBRASI R, IERSEL L V, KELK S, et al. The complexity of the single individual SNP haplotyping problem[J]. Algorithmica, 2007, 49(1):13-36.
[11] WANG Ruisheng, WU Lingyun, LI Zhenping, et al. Haplotype reconstruction from SNP fragments by minimum error correction[J]. Bioinformatics, 2005, 21(10):2456-2462.
[12] PANCONESI A, SOZIO M. Fast hare: a fast heuristic for single individual SNP haplotype reconstruction[C] //Proceedings of WABI-04. Bergen, Norway: Springer Press, 2004:266-277.
[13] GENOVESE L M, GERACI F, PELLEGRINI M. SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008, 5(4):492-502.
[14] LEVY S, SUTTON G, NG P C, et al. The diploid genome sequence of an individual human[J]. PLOS Biology, 2007, 5(10):2113-2144.
[15] BANSAL V, BAFNA V. HapCUT: an efficient and accurate algorithm for the haplotype assembly problem[J]. Bioinformatics, 2008, 24(16):i153-i159.
[16] MAZROUEE S, WANG W. FastHap: fast and accurate single individual haplotype reconstruction using fuzzy conflict graphs[J]. Bioinformatics, 2014, 30(17):i371-i378.
[17] 吴璟莉. 遗传多态性检测中组合优化问题的研究[D]. 长沙: 中南大学, 2008. WU Jingli. Research on the combinatorial optimization problem in detection of genetic diversities[D]. Changsha: Central South University, 2008.
[18] WU Jingli, LIANG Binbin. A fast and accurate algorithm for diploid individual haplotype reconstruction[J]. Journal of Bioinformatics and Computational Biology, 2013, 11(4):1350010.
[19] The International HapMap Consortium. The international HapMap project[J]. Nature, 2003, 426(6968):789-796.
[20] MYERS G. A dataset generator for whole genome shotgun sequencing[C] //Proceedings of ISMB-99. Heidelberg, Germany: AAAI Press, 1999:202-210.
[21] RICHTER D C, OTT F, AUCH A F, et al. MetaSim: a sequencing simulator for genomics and metagenomics[J]. Plos One, 2008, 3(10):1-12.
[1] DENG Bin, ZHANG Zongbao, ZHAO Wenmeng, LUO Xinhang, WU Qiuwei. Cloud-edge collaborative and graph neural network based load forecasting method for electric vehicle charging stations [J]. Journal of Shandong University(Engineering Science), 2025, 55(5): 62-69.
[2] GAO Junjian, LIAO Zhuhua, LIU Yizhi, ZHAO Yijiang. Hierarchical multi-agent reinforcement learning based route guidance method combining personalization and signal control [J]. Journal of Shandong University(Engineering Science), 2025, 55(3): 34-45.
[3] LI Feng, WEN Yimin. Multi-scale visual and textual semantic feature fusion for image captioning [J]. Journal of Shandong University(Engineering Science), 2025, 55(3): 80-87.
[4] ZHOU Yanbing, MA Shilun, WEN Yimin. Concept drift detection based on graph structure [J]. Journal of Shandong University(Engineering Science), 2025, 55(2): 88-96.
[5] Ying LI,Jiankun WANG. The classification of mild cognitive impairment based on supervised graph regularization and information fusion [J]. Journal of Shandong University(Engineering Science), 2023, 53(4): 65-73.
[6] Tongyu JIANG, Fan CHEN, Hongjie HE. Lightweight face super-resolution network based on asymmetric U-pyramid reconstruction [J]. Journal of Shandong University(Engineering Science), 2022, 52(1): 1-8.
[7] GONG Lejun, YANG Lu, GAO Zhihong, LI Huakang. Construction of knowledge graph of relationship between LncRNA and diseases [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 26-33.
[8] LIN Xiaowei, CHEN Lifei. Community detection using nonnegative matrix factorization with structure extension [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 57-64.
[9] ZHANG Qinyang, LI Xu, YAO Chunlong, LI Changwu. Aspect-level sentiment classification combined with syntactic dependency information [J]. Journal of Shandong University(Engineering Science), 2021, 51(2): 83-89.
[10] Jiangli DUAN,Xin HU. Semantic relation recognition for natural language question answering [J]. Journal of Shandong University(Engineering Science), 2020, 50(3): 1-7.
[11] Wenkai ZHANG,Ke YU,Xiaofei WU. Entity recommendation based on normalized similarity measure of meta graph in heterogeneous information network [J]. Journal of Shandong University(Engineering Science), 2020, 50(2): 66-75.
[12] Jialin SU,Yuanzhuo WANG,Xiaolong JIN,Xueqi CHENG. Entity alignment method based on adaptive attribute selection [J]. Journal of Shandong University(Engineering Science), 2020, 50(1): 14-20.
[13] Yuanxi YAO. Analysis of wind power convergence trend quantitation based on sub-scene reconstruction [J]. Journal of Shandong University(Engineering Science), 2019, 49(6): 86-92.
[14] Yun HU,Shu ZHANG,Hui LI,Kankan SHE,Jun SHI. Recommendation algorithm based on trust network reconfiguration [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 42-46.
[15] Xiaodan WANG,Mingming GAO. Polyaniline modified graphene layers/graphite plate electrode for supercapacitor [J]. Journal of Shandong University(Engineering Science), 2018, 48(6): 132-136.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] SHI Lai-shun,WAN Zhong-yi . Synthesis and performance evaluation of a novel betaine-type asphalt emulsifier[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 112 -115 .
[2] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[3] LI Hui-ping, ZHAO Guo-qun, ZHANG Lei, HE Lian-fang. The development status of hot stamping and quenching of ultra high-strength steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 69 -74 .
[4] SUN Cong-zheng,GUAN Cong-sheng,QIN Jing-yu,CHENG Chuan . The structure and performances of the electroless Ni-P alloy coating on aluminum alloy[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(5): 108 -112 .
[5] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 108 -112 .
[6] HU Tian-liang,LI Peng,ZHANG Cheng-rui,ZUO Yi . Design of a QEP decode counter based on VHDL[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 10 -13 .
[7] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[8] WANG Shan,LI Tian-ze . A new method for the control of a wound-rotor induction machine[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 86 -89 .
[9] LUO Yun-hu,XING Li-dong,WANG Qin,LIU Hai-chun,WENG Xiao-guang . Coordination of bidding strategies for two kinds of interruptible load reserve markets on demand side[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 77 -80 .
[10] SUN Zong-yao,LIU Yun-gang . Adaptive output feedback stabilization for a class of second-dimensional uncertain nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(5): 34 -39 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd