بخشی از مقاله
مقایسه عملکرد زبان برنامه نویسی C با FORTRAN براي مطابقت رشته هاي DNA
با رابط موازي سازي OpenMP
چکیده
در این مقاله سعی داریم, تا با استفاده از یک الگوریتم موازي به نام کامبت که زاتـا یـک الگـوریتم سـریال است را به نحوة که در ادامه به شرح آن می پردازیم، قسمتی هاي از الگوریتم را به صـورت مـوازي بـا رابـط موازي سازي OpenMP پیاده سازي کنیم, تا با استفاده از آن در سطح DNA پروتئین براي مطابقت رشته DNA در ناحیه کد , دو زبان برنامه نویسی C و FORTRAN را با رابط مـوازي سـازي OpenMP، مـورد مقایسه قرار دهیم. اما هدف از ارائه این مقاله این است, که کـدام یـک زمـان کمتـري را بـراي مطابقـت دو رشته DNA ناحیه کد در سطح پروتئین ارائه می دهد.در حالی زمان اجراي برنامه در هر دو زبان با تعـداد پردازنده اي متفاوت مورد بررسی قرار میگردند، تا در پایان این مقاله به هدف اصلی مـورد نظرمـان کـه، از کدام یک از این دو زبان در آزمایشات آینده براي مطابقت دو رشته DNA استفاده نماییم.
واژگان کلیدي: زبان برنامه نویسی , OpenMP , FORTRAN , C مطابقت رشته DNA
مقدمه
زبان C
زبان C در آزمایشگاه BELL در اوایل دهه 1970 به منظور تکمیل و بازنویسی نسخه اولیه سیستم عامل UNIX طراحی شده و امروزه نسخ مختلفی از زبان C بوجود آمده است .گرچه C یک زبان سطح بالا است ولی غالبا به عنوان زبان برنامه نویسی سیستم و یا براي رفع نیازهایی که در گذشته به کمک زبان اسمبلی برطرف می شدند استفاده می شود .همچنین بسیاري از نرم افزارهاي اساسی کامپیوتر به این زبان نوشته می شوند.
FORTRAN
فرترن اولین زبان سطح بالا است که تولید آن در سال 1954 به سرپرستی جان بـاکوز بـه منظـور ایجـاد یـک زبـان علمـی در شرکت IBMشروع شد در سال 1957 روي IBM 704 معرفی گردید که بالغ بر 2.5 میلیون دلار هزینه برداشت .با استفاده از این زبان حل معادلات ریاضی بسیار آسان گردید و بسیار مورد استقبال قرار گرفت .این زبان در اکثر کامپیوترهاي بزرگ و کوچک مورد استفاده قرار می گیرد و همین استقبال فوق العاده سبب شد تا کار تهیه استاندارد در سال 1962 براي آن شروع شود که یکی از آن ها را نسخه پایه و دیگري را نسخه کامل یا گسترش یافته می نامند .استاندارد زبان فرترن در سال 1966 مورد پذیرش سازمان استاندارد آمریکا قرار گرفت و این اولین زبانی بود که به صورت استاندارد درآمد .برنامه هایی که به این زبان در یک کامپیوتر نوشته می شود معمولا به سادگی در سایر کامپیوترها نیز قابل استفاده می باشد.
مطابقت رشته هايDNA
در داخل هسته تمامی سلول هاي بدن ما یک کامپیوتر ریز و باهوش که بسیار قوي تر از تمامی کامپیوترهاي جهان است قـرار دارد. این کامپیوتر ریز در واقع همان DNA یا ماده ژنتیکی ما است، که تمامی اطلاعات مربوط به زندگی و عملکرد ما را برنامـه ریزي و تنظیم می کند. این موجودات زنده در فرآیند تکامل به گونه هاي عالی تري نسبت به قبل تبـدیل مـی شـوند. در ایـن تکامل تبدیل رشته هاي DNA که نگهدارنده اطلاعات ژنتیکی هر ارگانیسم می باشد، دچار تغییراتی می شوند. این تغییرات به گونه اي است که یک نوکلئوتیدي که شامل ساختاري از آدنین ، تیمین ، سیتوزین و گوانین مـی باشـد بـا نوکلئوتیـد دیگـري جایگزین گردد و یا یک نوکلئوتید دیگري اضافه و یا حتی باعث حذف آن شود.این گونه از تغییرات با استفاده از مطابقت رشـته هايDNA به دست می آید. در حالت کلی مسئله مطابقت دو رشته ، پیدا کردن بیشترین میزان شباهت بـین دو رشـته DNA می باشد که یکی از آن رشته ها احتمالا از حذف، اضافه و یا حتی جایگزین نوکلئوتیدي در رشته دیگري به دست آمـده اسـت. بر حسب تعداد جفت یکسان ، تعداد جایگزینی ها و تعداد حدف یا اضافه ، یک مطابقت امتیازدهی می شود. هر جفت بر طبـق مدل ساختاري واحدDNA میزان آدنین و تیمین برابر است زیرا بازهاي آدنین در یکـی از دو رشـته همیشـه بـه تیمـین رشـته مقابل می پیوندد. به طور مشابهی میزان گوانین با سیتوزین نیز برابر است، زیرا دو بازه در مولکول DNA ، همراه به هـم پیونـد می خورند. از این رو، اگر دو رشته مولکولی DNA با شکستن پیوند هاي بین بازها جدا شوند، هـر رشـته تمـام اطلاعـات لازم جهت سنتز رشته مقابل را فراهم می کند. بنابراین مطابقتی بهینه و ایده آل است که بهترین و بالاترین امتیاز ممکـن را داشـته باشد. از الگوریتم هاي مطابقت می توان براي مقایسه رشته هاي DNA یا RNA یا اسید آمینه استفاده کـرد. ولـی اسـتفاده از مطابقت رشته هاي اسید آمینه بسیار گسترده است. براي محاسبات دقیق تر و کلی مطابقت، الگوریتمی بر مبناي برنامه سـازي پویا توسط نیدلمن و وانچ و براي مطابقت هاي جزئی تر اسمیت-واتر ارائه شد. گوتر الگوریتم هاي ارائـه شـده را بـه ازاي جـاي خالی آفین بهینه کرد و سپس میرز و میلر بر اساس الگوریتمی از هیرسبرگ الگوریتمی با فضاي خطی براي مطابقـت دو رشـته ارائه کردند. یکی دیگري از مدل هایی که براي مطابقت رشته DNA ناحیه مطرح می شود مطابقـت در سـطح DNA پـروتئین است. مطابقت سطح DNA پروتئین که توسط هین ارائـه شـده اسـت همزمـان تغییـرات تکـاملی در سـطح DNA و تغییـرات احتمالی در سطح پروتئین را در نظر می گیرد. سپس پدرسن الگوریتمی بهینه تر براي ایـن مـدل ارائـه داد. بهینـه تـرین ایـن
الگوریتم ها عموما داراي پیچیدگی زمان O(mn) و حافظه اي O(m+n) هستند که m و n طول دو رشته ورودي الگوریتم مـی باشد. براي رشته هاي طولانی استفاده از این الگوریتم ها براي مطابقت رشته ها با توجه بـه پیچیـدگی زمـانی آن عمـلا امکـان پذیر نیست. بدین منظور الگوریتم هاي اکتشافی مختلفی مثل BLAST و FASTA ارائه شد که علی رغـم سـرعت اجـراي بـالا لزوما مطابقت بهینه را نمی دهند. زیرا به خاطر اینکه هر دو آن ها الگوریتم اکتشافی هستند دقت کم تري دارد و ممکـن اسـت بعضی از مطابقت ها را پیدا نکنند و از دست بدهنـد. راه دیگـري افـزایش سـرعت اجـراي الگـوریتم هـاي مطابقـت اسـتفاده از الگوریتم هاي موازي است. الگوریتم هاي موازي مختلفی براي محاسبه مطابقت دو رشته بر مبناي برنامه سازي پویا ارائـه شـده است. ادمیستون و همکاران اولین الگوریتم موازي مطابقت رشته را ارائه کردند که به طور خطـی سـرعت را افـزایش مـی دهـد. هانگ اولین الگوریتمی که هم از نظر زمان و هم از نظر حافظه بهینـه اسـت را ارائـه کـرده اسـت.اخیـرا آلـورو و همکـاران نیـز مطابقتی که از نظر زمان و حافظه بهینه است بر مبناي تقسیم مستقیم مطابقتها بهینـه بـراي محاسـبه مـوازي ارائـه داده انـد. تاکنون هیچ الگوریتم موازي براي مطابقت در سطح پروتئین ارائه نشده است. در این مقاله یک الگوریتم موازي بـراي ایـن کـار ارائه می گردد.این مقاله به این صورت سازماندهی می گردد: در ابتدا که در مقدمه مشاهده گردیـد یـک مقدمـه مختصـري از زبان برنامه نویسی C با FORTRAN همچنبین دنیـاي DNA شـرح داده شـد. در بخـش روش تحقیـق, مـا نحـوه عملکـرد الگوریتم کامبت و ویژگی هاي رابط موازي سازي OpenMP را مطرح می کنـیم.و در بخـش یافتـه هـا عملکـرد زبـان برنامـه نویسی C و FORTRAN را در اجراي الگوریتم کامبت با رابط موازي سازي OpenMP بیان می کنیم و در بخش پایانی نتایج به دست آمده از این دو زبان برنامه نویسی را تحلیل و مقایسه آنها با یکدیگر ارائه می گردد.
روش تحقیق
در این مقاله براي بررسی نتایج از رشته هاي NM-009791 به طول 9363 نوکلئوتید و XM-422197 به طول 9078 نوکلئوتید (بر گرفته از پایگاه اطلاعاتی (NCBI استفاده شده است. در ابتدا مطابقت این رشته هاي DNA بررسی شده است. سپس الگوریتم موازي براي مطابقت این رشته هاي DNA ارائه گردیده است.مطابقت سطح DNA پروتئین دو رشته DNA ناحیه کد کننده ، مطابقت بهتري نسبت به مطابقت سطح DNA یا سطح پروتئین می دهد، و اولین و بهترین الگوریتم ترکیبی براي این نوع مطابقت توسط پدرسن با نام کامبت ارائه شده است. تاکنون هیچ الگوریتم موازي براي این کار ارائه نشده است. بنابراین کامبت براي موازي سازي مناسب است. الگوریتم کامبت داراي پیچیدگی زمان و حافظه از درجه 2 است. بنابراین براي رشته هاي طولانی DNA زمان اجرا به شدت افزایش پیدا می کند. براي حل این مشکل می توان از موازي سازي استفاده نمود. در ادامه الگوریتم موازي بر اساس الگوریتم کامبت ارائه می گردد. در الگوریتم کامبت موازي با محاسبه موازي جدول هاي مطابقت، زمان اجراي مطابقت را بهبود می یابد. این الگوریتم براي مدل MIMD بر اساس دسته بندي سیستم هاي کامپیوتري فلاین جوهانسون می باشد ، نوع کلاستر پردازش موازي ارائه شده است. در این الگوریتم پردازنده ها ماتریس هاي امتیاز مطابقت را به صورت موازي، قطري حساب می کنند همچون . BLOSUM62 بدین منظور این ماتریس ها به صورتی که در ادامه توضیح داده می شود به زیر ماتریس هاي کوچک تر تبدیل شده و پردازش آن ها بین پردازنده ها تقسیم می شود. در اینجا زیر ماتریس هایی که در یک گام توسط یک پردازنده پردازش می شود را بلاك گوییم و هر گام از محاسبه موازي بلاك ها را یک مرحله می گوییم. اگر سیستم موازي ما P پردازنده داشته باشد آنها را از صفر تا P-1 شماره گذاري می کنیم. می خواهیم مطابقت دو رشته a به طول n و b به طول m را حساب کنیم. فرض می کنیم n ضریبی از تعداد پردازنده ها P باشد. پردازنده iام مسئول پردازش سطرهاي (1) ماتریس امتیاز است
(1) (i+ به ازاي (2) (2)
در طول پردازش موازي هر پردازنده یا بیکار است یا در حال پردازش بلاك خودش است. اگر پردازش یک بلاك تمام شد، هیچ پردازنده دیگري آن را دوباره محاسبه نمی کند. هنگامی که پردازنده iام پردازش مرحله S را تمام کرد، اطلاعات سطر پایین خود را به پردازنده بعدي ارسال می کند تا آن پردازش مرحله S+1 را بتواند آغاز کند. در شکل((1 بلاك ها با شماره مرحله پردازش موازي شان شماره گذاري شده اند. پردازش موازي از پردازنده 1 آغاز شده و بلاکی که با شماره 1 در شکل((1,2نشان داده شده است را بر اساس الگوریتم ترتیبی محاسبه می کند. این بلاك قابل محاسبه است چون مقادیر اولیه آن فراهم می باشد ولی محاسبه بقیه بلاك ها ممکن نیست. پس بقیه پردازنده ها در اولین مرحله بیکاري هستند. با اتمام محاسبه این بلاك سطرهاي مورد نیاز محاسبه بلاك پایینی اش را پردازنده اول به پردازنده دوم ارسال می کند. در مرحله S=2 اطلاعات کافی براي محاسبه بلاك هاي همسایه این بلاك فراهم شده است. این بلاك ها با شماره 2 در شکل(1,2 )نشان داده شده اند. دو بلاك همسایه به صورت موازي توسط دو پردازنده محاسبه می شوند.به همین صورت محاسبه بلاك ها به صورت قطري ادامه می یابد. در مرحله S=Pام تمامی P پردازنده به طور موازي کار می کنند، زیرا قطر دقیقا شامل P پردازنده است. اگر تعداد ستون هاي تقسیم بلاکی را C در نظر بگیریم پردازش موازي هنگامی خاتمه می یابد که تمامی بلاك محاسبه شده اند. در شکل (1)تقسیم بلاکی ماتریس ها به ازاي 8 پردازنده و C=15نشان داده شده است و در شکل (2) تقسیم بلاکی ماتریس ها به ازاي 16 پردازنده و C=30 نشان داده شده است (سید حسین سلطانی و همکاران .(2007
شکل :1 مراحل محاسبه بلاك ها با 8 پردازنده
شکل :2 مراحل محاسبه بلاك ها با 16 پردازنده
زبانی که براي پیاده سازي الگوریتم کامبت در نظر گرفته ایم زبان C و FORTRAN است که با استفاده از یک رابط برنامه مواز ي سازي به نام OpenMP بتوانیم بخش هاي از الگوریتم که قابلیت موازي سازي دارند را به صورت موازي برنامه نویسی
