Haplotype Estimation Using Polynomial Optimization Relaxation

Majidian, S.; Kahaei, M. H.

Haplotype Estimation Using Polynomial Optimization Relaxation

Document Type : Original Article

Authors

School of Electrical Engineering, Iran University of Science & Technology, Tehran, Iran

Abstract

This paper is dedicated to investigating haplotype estimation based on DNA sequences. The proposed algorithm named as (HapLas) is introduced using relaxation of polynomial optimization based on the Lasserre technique. This algorithm is based on the discrete structure of optimization problem of haplotype estimation which is mapped to a continuous space using the measure theory. Then, relaxation is performed via the properties of the moment matrix. Simulation results show that the proposed algorithm improves the reconstruction rate of the haplotype about five percent in comparison to the SDhaP and RefHap. This is achieved at the cost of increasing the running time and computational complexity which can practically be ignored in medicine.

Keywords

References

[1] مهری ملالو، فاطمه زارع میرک آباد. «پیدا کردن موتیف در نواحی بالادست ژن‌های هم بیان بر اساس الگوریتم بهینه سازی فاخته و سرمایش تدریجی» مجله مهندسی برق دانشگاه تبریز. 46، 333-344،پاییز 1395.

[2] رسول صادقی، فردین ابدالی محمدی. «ارائه یک روش یادگیری ویژگی ترکیبی مبتنی بر الگوریتم شبیه‌سازی تبرید و برنامه‌نویسی ژنتیک (مطالعه موردی: تشخیص بدخیمی سرطان سینه) » مجله مهندسی برق دانشگاه تبریز. 48، 127-136 بهار 1397.

[3] B. Alberts, K. Roberts, J. Lewis, D. Bray, K. Hopkin, A. Johnson, P. Walter, and M. Raff,. Essential Cell Biology. Garland Science, 2013.

[4] J. Shendure, S. Balasubramanian, G. Church, W. Gilbert, J. Rogers, J. Schloss, and R. Waterston, “DNA sequencing at 40: past, present and future.” Nature, Vol. 550, 2017.

[5] A. Motahari, G. Bresler and D. Tse, “Information theory of DNA shotgun sequencing.” IEEE Transactions on Information Theory. Vol. 59, pp.6273-6289, 2013.

[6] C. Cai, S. Sanghavi, and H. Vikalo “Structured low-rank matrix factorization for haplotype assembly.” IEEE Journal of Selected Topics in Signal Processing Vol. 10.4, pp. 647-657, 2016.

[7] M. Snyder, A. Adey, J. Kitzman, and J. Shendure, “Haplotype-resolved genome sequencing: experimental methods and applications”. Nature Reviews. Vol. 16(6), 2015.

[8] G. Klau, and T. Marschall. “A guided tour to computational haplotyping.” Conference on Computability in Europe. Springer, 2017.

[9] V. Bansal and V. “Hapcut: an efficient and accurate algorithm for the haplotype assembly problem” Bioinformatics, Vol. 24(16), 2008.

[10] E. Berger, D. Yorukoglu, J. Peng, and B. Berger, “Haptree: A novel bayesian framework for single individual polyplotyping using NGS data” PLoS computational biology, Vol. 10(3), 2014.

[11] J. Duitama, G. McEwen, T. Huebsch, S. Palczewski, S. Schulz, K. Verstrepen, E. Suk, and M. Hoehe, “Fosmid-based whole genome haplotyping of a hapmap trio child: evaluation of single individual haplotyping techniques” Nucleic acids research, Vol. 40(5), 2011.

[12] H. Si, H. Vikalo, and S. Vishwanath. “Information-theoretic analysis of haplotype assembly” IEEE Transactions on Information Theory, Vol. 63(6), 2017.

[13] J. Lasserre, “Global optimization with polynomials and the problem of moments.” SIAM Journal on Optimization Vol. 11.3, pp796-817, 2001.

[14] D. Henrion, J. Lasserre “GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi.” ACM Transactions on Mathematical Software, Vol. 29.2, pp165-194, 2003.

[15] F. Geraci, “A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem,” Bioinformatics, Vol. 26.18, pp.2217–2225, 2010.

[16] M. Laurent, “Sums of squares, moment matrices and optimization over polynomials.” Emerging applications of algebraic geometry. Springer New York, pp. 157-270, 2009.

[17] H. Royden, and P. Fitzpatrick. Real Analysis. Pearson. 2010.

[18] P. Parrilo, “Semidefinite programming relaxations for semialgebraic problems.” Mathematical programming Vol. 96.2, pp. 293-320, 2003.