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)

665

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] Guoxin WANG,Fengdong CHEN,Guodong LIU. Feature extraction method of color pseudo-random coded structured light [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 55-60.
[2] YE Ziyun, YANG Jinfeng. A finger-vein recognition method based on weighted graph model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 103-109.
[3] HE Wenjie, HE Weichao, SUN Quansen. Parallelization and GPU acceleration of compressive sensing reconstruction algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 110-114.
[4] ZHANG Zhenyue, LI Fei, JIANG Mingyan. Unsupervised face image feature extraction based on low-rank representation projection [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(1): 15-20.
[5] ZHANG Guojian, YU Chengxin, GUO Guangli. Application of digital close-range photogrammetry in the deformation observation of check gate [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(6): 46-51.
[6] DENG Junwu, ZHANG Yumin, ZHANG Hongdi, DU Xiaokun. Fault diagnosis and fault-tolerant control methods of X-tail UAV [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 166-172.
[7] WANG Mengyuan, ZHANG Xiong, MA Liang, PENG Kaixiang. Fault diagnosis for industrial processes based on causal topological graph [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 187-194.
[8] LI Minghu, LI Gang, ZHONG Maiying. Application of dynamic kernel principal component analysis in unmanned aerial vehicle fault diagnosis [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 215-222.
[9] LIU Zhuo, WANG Tianzhen, TANG Tianhao, FENG Yefan, YAO Junqi, GAO Diju. A fault diagnosis and fault-tolerant control strategy for multilevel inverter [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 229-237.
[10] WANG Mingyu, SU Liqing, ZHANG Shaojun, WANG Yu. Fe3O4 magnetic dispersive solid-phase extraction with graphene for determination of organochlorine pesticides contaminants in water [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 117-123.
[11] JIN Peipei, SUN Fengrong, LIU Fanglei, YAO Guihua. Cardiac cycle estimation of echocardiography with speckle tracking [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(2): 94-99.
[12] JIA Hongshuai, ZHAO Xuejin, HU Tianliang, ZHANG Chengrui. Image distortion correction technology of mask image projection stereolithography [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 97-103.
[13] TIAN Feng, LIU Zhuoxuan, SHANG Fuhua, SHEN Xukun, WANG Mei, WANG Haochang. Image annotation refinement based on contextual graph diffusion [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 1-6.
[14] YANG Yuanhui, LI Guodong, WU Chunfu, WANG Xiaolong, CAI Xiaowei. Hand-eye calibration and visual servo control for mobile manipulator [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(5): 54-63.
[15] HOU Yan, YANG Meng. Highly efficient algorithm for tracking explicit surface to process complex topological events [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 15-20.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[2] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[3] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[4] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 104 -107 .
[5] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[6] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 131 -136 .
[7] LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[8] ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .
[9] ZHAO Zhi-guang,WANG Deng-jie,TIAN Yun-fei . Roadbed settlement based on the gray theory[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 86 -88 .
[10] YAO Zhan-yong,SHANG Qing-sen,ZHAO Zhi-zhong,JIA Zhao-xia . The influence analysis of the semirigid asphalt pavement configuration stress and distortion by interface conditions[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 93 -99 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd