22242

تخمين هاپلوتايپ با استفاده از تكميل ماتريس

دكتري

مخابرات - سيستم

13941

1399/5/7

دكتر محمدحسين كهائي

برق

به منظور تشخيص الگوي بيماري­ها مي­بايست از داده­هاي زيستي كه به طور انبوه در دسترس قرار دارد، به طور مناسبي استفاده نمود. به منظور تحليل اين داده­ها مي­توان از راهبردهاي پردازش سيگنال استفاده كرد. در سال­هاي اخير، پردازش سيگنال توانسته است با حل مسائل مورد نياز پزشكان و زيست‌شناسان نقش مهمي در نجات جان انسان­ها و موجودات زنده ايفا نمايد. به منظور بررسي بيماري­هاي ژنتيكي، تخمين هاپلوتايپ ضروري است. همچنين، در طراحي دارو (به منظور درمان اختصاصي متناسب با ژنتيك هر فرد) و سلول درماني تخمين هاپلوتايپ مورد نياز است. هدف اصلي اين رساله، ارائه روش نويني جهت كاهش خطاي تخمين هاپلوتايپ با استفاده از تكميل ماتريس است. در اين مساله، داده‌ي ورودي، توالي نوكلئوتيدهاي رشته‌ي DNA است كه براي حالت ديپلويد (موجودات با K=2 سري كروموزم همسان) و پلي‌پلويد (K>2) جداگانه بررسي شده است. به منظور حل مساله تخمين هاپلوتايپ ديپلويد، در ابتدا سه الگوريتم HapSVT، HapNuc و HapOPT بر مبناي سه راهبرد متداول تكميل ماتريس پيشنهاد شده است. نتايج شبيه‌سازي نشان داد كه الگوريتم HapOPT در مقايسه با الگوريتم‌هاي مرجع (از جمله HapCut2) بهترين عمل‌كرد را از نظر نرخ بازسازي براي داده‌هاي توليد شده و بهترين عمل‌كرد را از نظر معيار AN50 براي داده‌هاي واقعي دارد. از آنجايي كه همراه با توالي نوكلئوتيدها، تخميني از ميزان خطاي خوانش هر نوكلئوتيد نيز در دسترس است، يك بهينه‌سازي جديد (NuWeC)، بر اساس نرم هسته‌اي با قيد وزن‌دهي شده معرفي شده است تا از چنين اطلاعاتي به درستي استفاده گردد. نتايج شبيه‌سازي حاكي از آن است كه استفاده مناسب از احتمال خطاي هر درايه در بهينه‌سازي پيشنهادي NuWec، منجر به بهبود 2dB در خطاي بازسازي ماتريس ناقص در مقايسه با بهينه‌سازي نرم هسته‌اي شده است. در اين رساله، براي مساله بهينه‌سازي پيشنهادي، كران خطا به صورت تابعي از نرم چهارم بردار وزن‌ها محاسبه شده است. همچنين، الگوريتم HapWeC به منظور تخمين هاپلوتايپ بر مبناي بهينه‌سازي ذكر شده، پيشنهاد گرديد. در شبيه‌سازي‌ها، مشاهده گرديد كه الگوريتم پيشنهادي HapWec، بهتر از الگوريتم‌هاي مرجع و الگوريتم HapOPT عمل كرده است، اين بدان علت است كه HapWec از اطلاعات اضافه (احتمال خطاي نوكلئوتيد) استفاده مي‌كند. در اين رساله به منظور حل مساله تكميل ماتريس رتبه يك، استفاده از بهينه‌سازي چندجمله‌اي و ريلكس‌سازي آن با استفاده از تئوري اندازه مورد بحث قرار گرفت. برمبناي اين تئوري، الگوريتم HapLas معرفي شد اما اين الگوريتم داراي پيچيدگي محاسباتي بالا (زمان اجراي زياد) است. مهمترين نوآوري اين رساله، تحليل تابع تصحيح كمينه‌ خطا (MEC) به عنوان يك تابع‌ هدف و معيار ارزيابي دقت براي مساله تخمين هاپلوتايپ است. ضمن ارائه يك قضيه، نشان داده شد كه هنگامي كه بيش از نصف توالي‌هاي پوشش‌دهنده‌ي يك درايه‌ي هاپلوتايپ، خطا باشند، استفاده از راهبرد MEC منجر به رسيدن به هاپلوتايپ ناصحيح مي‌شود. همچنين، با بررسي شرايط قضيه به صورت احتمالي، مشاهده شد كه براي داده‌هاي توالي‌يابي با پوشش 10 و دستگاه‌ توالي‌ياب با نرخ خطاي دو درصد، الگوريتم‌هاي با محوريت MEC، قادر به تخمين هاپلوتايپ دقيق نخواهند بود. همچنين، مشاهده شد كه افزايش طول بلوك هاپلوتايپ، به ازاي احتمال خطاي نوكلئوتيد كمتري منجر به هاپلوتايپ ناصحيح مي‌شود. نوآوري ديگر اين رساله، پيشنهاد اولين الگوريتم تخمين هاپلوتايپ پلي‌پلويدي با استفاده از داده‌هاي فن‌آوري توالي‌يابي شركت 10X Genomics مي‌باشد. اين الگوريتم با نام Hap++ بر مبناي خوشه‌بندي انتقال ميانگين و خوشه‌بندي برش نرمال شده مي‌باشد. علاوه بر اين، الگوريتم Hap10 نسخه بهبود يافته الگوريتم Hap++، با استفاده از بهينه‌سازي لاگرانژي پيشنهاد گرديد. نتايج شبيه‌سازي با استفاده از داده‌هاي توليد شده، حاكي از آن است كه الگوريتم پيشنهادي توانسته است عملكرد بسيار بهتري از ديد نرخ بازسازي (15 % بهبود) و نرخ خطاي برداري (كاهش به يك پنجم) به ازاي متوسط طول بلوك هاپلوتايپ كمتري نسبت به الگوريتم مرجع (SDhaP) ارائه دهد. همچنين استفاده از الگوريتم Hap10 منجر به بهبود تخمين هاپلوتايپ در ازاي افزايش پيچدگي محاسباتي در مقايسه با الگوريتم Hap++ مي‌شود.

1399/05/11

Haplotype estimation using matrix completion

7/28/2020 12:00:00 AM

In order to detect the pattern of disease, it is essential to use the available biological datasets. To analyze such data, signal processing approaches can be used. In recent years, signal processing has been able to play an important role in saving both human's and creatures' lives. In order to investigate genetic disease, haplotype information is essential. Moreover, the haplotype is needed in drug design, personalized medicine, and cell therapy. The principal goal of this thesis is to propose a new method for decreasing the error of haplotype estimation using matrix completion. In this problem, the input is the nucleotides sequence of DNA which is called a sequencing read and is considered for both diploids and polyploids. To solve the haplotype assembly problem, three algorithms called HapOPT, HapNuc, and HapSVT are three well-known methods for matrix completion. Simulation results show that HapOPT achieves the best performance compared to the newest algorithm in the literature, HapCut2, in terms of reconstruction rate for the simulated data. Since the DNA sequencing devices provide an estimate of sequencing, we propose a new optimization problem called the NuWec using the Nuclear norm with weighted constraints. Simulations show that by exploiting the sampling error, we are able to reconstruct partially observed matrices more accurately (2dB) compared to the nuclear norm. We also derive the error bound for the proposed optimization as a function of the fourth norm of the weights. Furthermore, in order to solve the rank-one matrix completion problem, the measure theory is used to relax the corresponding polynomial optimization. This approach leads to introducing the HapLas algorithm, which is associated with high computational burden. The most important innovation of this thesis is analyzing the Minimum Error Correction (MEC), function, which is also a criterion for evaluation of estimation accuracy. By proving a theorem, we show that when more than half of the reads covering of a haplotype entry are with error, the use of MEC approach will lead to estimating inaccurate haplotypes. Another contribution of this thesis is to propose the first haplotyping algorithm for the barcoded reads produced by the 10X Genomics device. Happp is the algorithm that is developed for this case using the mean shift and normalized cut clustering. The simulations show 15% improvement in the reconstruction rate with decreasing the vector error rate to one fifth compared to the reference algorithm (SDhaP).

تكميل ماتريس , تجزيه مقدار تكين , تخمين , بيوانفورماتيك , هاپلوتايپ , دي ان آ

Matrix completion , Singular value decomposition , Estimation , Bioinformatics , Haplotype , DNA