تخمین هاپلوتایپ با استفاده از ریلکس‌سازی بهینه‌سازی چندجمله‌ای

نوع مقاله : علمی-پژوهشی

نویسندگان

دانشکده مهندسی برق- دانشگاه علم و صنعت ایران

چکیده

این مقاله به بررسی تخمین هاپلوتایپ با استفاده از داده‌های توالی DNA می‌پردازد. الگوریتم پیشنهادی با استفاده از ریلکس‌سازی بهینه‌سازی چندجمله‌ای به روش Lasserre  با نام HapLas  معرفی می‌شود. این الگوریتم برپایه استفاده از ساختار گسسته مساله بهینه‌سازی تخمین هاپلوتایپ می‌باشد که با استفاده از تئوری اندازه به یک فضای پیوسته نگاشت می‌گردد. سپس با استفاده از خواص ماتریس ممان، ریلکس‌سازی انجام می‌گیرد. نتایج شبیه‌سازی نشان می‌دهد که استفاده از الگوریتم پیشنهادی منجر به بهبود نرخ بازسازی هاپلوتایپ در مقایسه با الگوریتم‌های متداولSDhaP  و RefHap در حدود 5 درصد می‌گردد. این بهبود به‌ازای افزایش قابل ملاحظه زمان اجرا و پیچیدگی محاسبات حاصل می‌شود به‌طوری که در کاربردهای پزشکی قابل صرف‌نظرکردن است.

کلیدواژه‌ها


عنوان مقاله [English]

Haplotype Estimation Using Polynomial Optimization Relaxation

نویسندگان [English]

  • S. Majidian
  • M. H. Kahaei
School of Electrical Engineering, Iran University of Science & Technology, Tehran, Iran
چکیده [English]

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. 

کلیدواژه‌ها [English]

  • Haplotype
  • estimation
  • optimization
  • relaxation
  • positive definite matrix
  • measure theory
[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.