بخشی از مقاله
چکیده
در این مقاله سعی در این دارد تا با استفاده از الگوریتم موازی در سطح DNA پروتئین برای مطابقت در رشته های DNA را مورد بررسی قرار دهد، و یک الگوریتم موازی جدید به نام کامبت برای مطابقت رشته های DNA در سطح DNA پروتئین از لحاظ Speed-up ، نسبت به الگوریتم های دیگری هم چون الگوریتم های خطی که به حالت ایده آل نزدیک تر باشد را ارائه کند و مقایسه الگوریتم مذکور را با تعداد پردازنده های متفاوت را مورد بررسی قرار دهد.
کلمات کلیدی: الگوریتم موازی ، رشته های DNA ، سطح DNA پروتئین ، کامبت ، Speed-up
مقدمه
در داخل هسته تمامی سلول های بدن ما یک کامپیوتر ریز و باهوش که بسیار قوی تر از تمامی کامپیوترهای جهان است قرار دارد. این کامپیوتر ریز در واقع همان DNA یا ماده ژنتیکی ما است، که تمامی اطلاعات مربوط به زندگی و عملکرد ما را برنامه ریزی و تنظیم می کند. این موجودات زنده در فرآیند تکامل به گونه های عالی تری نسبت به قبل تبدیل می شوند. در این تکامل تبدیل رشته های DNA که نگهدارنده اطلاعات ژنتیکی هر ارگانیسم می باشد، دچار تغییراتی می شوند. این تغییرات به گونه ای است که یک نوکلئوتیدی که شامل ساختاری از آدنین ، تیمین ، سیتوزین و گوانین می باشد با نوکلئوتید دیگری جایگزین گردد و یا یک نوکلئوتید دیگری اضافه و یا حتی باعث حذف آن شود.[3] [2] [1]
این گونه از تغییرات با استفاده از مطابقت رشته هایDNA به دست می آید. در حالت کلی مسئله مطابقت دو رشته ، پیدا کردن بیشترین میزان شباهت بین دو رشته DNA می باشد که یکی از آن رشته ها احتمالا از حذف، اضافه و یا حتی جایگزین نوکلئوتیدی در رشته دیگری به دست آمده است. بر حسب تعداد جفت یکسان ، تعداد جایگزینی ها و تعداد حدف یا اضافه ، یک مطابقت امتیازدهی می شود. هر جفت بر طبق مدل ساختاری واحدDNA میزان آدنین و تیمین برابر است زیرا بازهای آدنین در یکی از دو رشته همیشه به تیمین رشته مقابل می پیوندد. به طور مشابهی میزان گوانین با سیتوزین نیز برابر است، زیرا دو بازه در مولکول DNA ، همراه به هم پیوند می خورند.[2] [1] از این رو، اگر دو رشته مولکولی DNA با شکستن پیوند های بین بازها جدا شوند، هر رشته تمام اطلاعات لازم جهت سنتز رشته مقابل را فراهم می کند. بنابراین مطابقتی بهینه و ایده آل است که بهترین و بالاترین امتیاز ممکن را داشته باشد. از الگوریتم های مطابقت می توان برای مقایسه رشته های DNA یا RNA یا اسید آمینه استفاده کرد. ولی استفاده از مطابقت رشته های اسید آمینه بسیار گسترده است. برای محاسبات دقیق تر و کلی مطابقت، الگوریتمی بر مبنای برنامه سازی پویا توسط نیدلمن و وانچ و برای مطابقت های جزئی تر اسمیت-واتر ارائه شد. گوتر الگوریتم های ارائه شده را به ازای جای خالی آفین بهینه کرد و سپس میرز و میلر بر اساس الگوریتمی از هیرسبرگ الگوریتمی با فضای خطی برای مطابقت دو رشته ارائه کردند. یکی دیگری از مدل هایی که برای مطابقت رشته DNA ناحیه مطرح می شود مطابقت در سطح DNA پروتئین است. مطابقت سطح DNA پروتئین که توسط هین ارائه شده است همزمان تغییرات تکاملی در سطح DNA و تغییرات احتمالی در سطح پروتئین را در نظر می گیرد.[4] سپس پدرسن الگوریتمی بهینه تر برای این مدل ارائه داد.[5]
بهینه ترین این الگوریتم ها عموما دارای پیچیدگی زمان O(mn) و حافظه ای O(m+n) هستند که m و n طول دو رشته ورودی الگوریتم می باشد. برای رشته های طولانی استفاده از این الگوریتم ها برای مطابقت رشته ها با توجه به پیچیدگی زمانی آن عملا امکان پذیر نیست. بدین منظور الگوریتم های اکتشافی مختلفی مثل BLAST و FASTA ارائه شد که علی رغم سرعت اجرای بالا لزوما مطابقت بهینه را نمی دهند. زیرا به خاطر اینکه هر دو آن ها الگوریتم اکتشافی هستند دقت کم تری دارد و ممکن است بعضی از مطابقت ها را پیدا نکنند و از دست بدهند. راه دیگری افزایش سرعت اجرای الگوریتم های مطابقت استفاده از الگوریتم های موازی است. الگوریتم های موازی مختلفی برای محاسبه مطابقت دو رشته بر مبنای برنامه سازی پویا ارائه شده است. ادمیستون و همکاران اولین الگوریتم موازی تطابق رشته را ارائه کردند[6] که به طور خطی سرعت را افزایش می دهد. هانگ اولین الگوریتمی که هم از نظر زمان و هم از نظر حافظه بهینه است را ارائه کرده است.[7]
×اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر
First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering×
. . . W W W . T D E C O N F . I R . . .
اخیرا آلورو و همکاران نیز مطابقتی که از نظر زمان و حافظه بهینه است بر مبنای تقسیم مستقیم مطابقتها بهینه برای محاسبه موازی ارائه داده اند.[8] تاکنون هیچ الگوریتم موازی برای مطابقت در سطح پروتئین ارائه نشده است. در این مقاله یک الگوریتم موازی برای این کار ارائه می گردد.
مواد و روش:
در این مقاله برای بررسی نتایج از رشته های NM-009791 به طول 9363 نوکلئوتید و XM-422197 به طول 9078 نوکلئوتید (بر گرفته از پایگاه اطلاعاتی (NCBI استفاده شده است. در ابتدا مطابقت این رشته های DNA بررسی شده است. سپس الگوریتم موازی برای مطابقت این رشته های DNA ارائه گردیده است.
مطابقت سطح DNA پروتئین دو رشته DNA ناحیه کد کننده ، مطابقت بهتری نسبت به مطابقت سطح DNA یا سطح پروتئین می دهد، و اولین و بهترین الگوریتم ترکیبی برای این نوع مطابقت توسط پدرسن با نام کامبت ارائه شده است.[5] تاکنون هیچ الگوریتم موازی برای این کار ارائه نشده است. بنابراین کامبت برای موازی سازی مناسب است. الگوریتم کامبت دارای پیچیدگی زمان و حافظه از درجه 2 است. بنابراین برای رشته های طولانی DNA زمان اجرا به شدت افزایش پیدا می کند. برای حل این مشکل می توان از موازی سازی استفاده نمود. در ادامه الگوریتم موازی بر اساس الگوریتم کامبت ارائه می گردد. در الگوریتم کامبت موازی با محاسبه موازی جدول های مطابقت، زمان اجرای مطابقت را بهبود می یابد. این الگوریتم برای مدل MIMD بر اساس دسته بندی سیستم های کامپیوتری فلاین جوهانسون می باشد[9] ، نوع کلاستر پردازش موازی ارائه شده است. در این الگوریتم پردازنده ها ماتریس های امتیاز مطابقت را به صورت موازی، قطری حساب می کنند همچون .[10] BLOSUM62 بدین منظور این ماتریس ها به صورتی که در ادامه توضیح داده می شود به زیر ماتریس های کوچک تر تبدیل شده و پردازش آن ها بین پردازنده ها تقسیم می شود. در اینجا زیر ماتریس هایی که در یک گام توسط یک پردازنده پردازش می شود را بلاک گوییم و هر گام از محاسبه موازی بلاک ها را یک مرحله می گوییم. اگر سیستم موازی ما P پردازنده داشته باشد آنها را از صفر تا P-1 شماره گذاری می کنیم. می خواهیم مطابقت دو رشته a به طول n و b به طول m را حساب کنیم. فرض می کنیم n ضریبی از تعداد پردازنده ها P باشد. پردازنده iام مسئول پردازش سطرهای (1) ماتریس امتیاز است
(1) + 1 n i تا n (i+1)
p p
به ازای (2)
(2) 0 ≤ i ≤ P − 1
در طول پردازش موازی هر پردازنده یا بیکار است یا در حال پردازش بلاک خودش است. اگر پردازش یک بلاک تمام شد، هیچ پردازنده دیگری آن را دوباره محاسبه نمی کند. هنگامی که پردازنده iام پردازش مرحله S را تمام کرد، اطلاعات سطر پایین خود را به پردازنده بعدی ارسال می کند تا آن پردازش مرحله S+1 را بتواند آغاز کند. در شکل 1 بلاک ها با شماره مرحله پردازش موازی شان شماره گذاری شده اند. پردازش موازی از پردازنده 1 آغاز شده و بلاکی که با شماره 1 در شکل 1و2 نشان داده شده است را بر اساس الگوریتم ترتیبی محاسبه می کند. این بلاک قابل محاسبه است چون مقادیر اولیه آن فراهم می باشد ولی محاسبه بقیه بلاک ها ممکن نیست. پس بقیه پردازنده ها در اولین مرحله بیکاری هستند. با اتمام محاسبه این بلاک سطرهای مورد نیاز محاسبه بلاک پایینی اش را پردازنده اول به پردازنده دوم ارسال می کند. در مرحله S=2 اطلاعات کافی برای محاسبه بلاک های همسایه این بلاک فراهم شده است. این بلاک ها با شماره 2 در شکل 1و2 نشان داده شده اند. دو بلاک همسایه به صورت موازی توسط دو پردازنده محاسبه می شوند.
