انتخاب ژن و طبقه بندی سلول های سرطانی بر پایه داده های ریزآرایه با استفاده از الگوریتم ترکیبی BPSO و BLDA

نوع مقاله: مقاله علمی فارسی

نویسندگان

1 کارشناس ارشد مهندسی برق، دانشکده مهندسی برق-دانشگاه صنعتی سهند-تبریز-ایران

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

3 - کارشناس ارشد مهندسی برق، دانشکده مهندسی برق-دانشگاه صنعتی سهند-تبریز-ایران

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

چکیده

داده های ریزآرایه در تشخیص و طبقه بندی انواع بافت های سرطانی نقش بسزایی دارند. در پژوهش های سرطان همیشه تعداد نسبتا کم نمونه ها در ریزآرایه باعث ایجاد مشکلاتی در طراحی طبقه بندها شده است. بنابراین داده های ریزآرایه قبل از طبقه بندی از طریق تکنیک های انتخاب ژن پیش پردازش و ژن های فاقد اطلاعات آن ها دور ریخته می شود. اساسا یک روش انتخاب ژن مناسب می تواند بطور موثر کارایی دسته بندی بیماری ها (سرطان) را بهبود بخشد. در این مقاله یک روش جدید بر پایه مدل ترکیبی ازدحام ذرات باینری (BPSO) و آنالیز تفکیک کننده خطی بیز (BLDA) جهت طبقه بندی داده های ریزآرایه با ابعاد بالا ارائه شده است. ابتدا موقعیت هر ذره بصورت بردار باینری و بصورت تصادفی نمایش داده می شود. بطوریکه هر بیت نشاندهنده یک ژن است. بیت صفر نشاندهنده این است که ویژگی (ژن) متناظر با آن انتخاب نشده و بیت یک نشاندهنده این است که ژن متناظر با آن انتخاب شده است. لذا موقعیت هر ذره بیانگر یک مجموعه ژن بوده و میزان تناسب هر ذره توسط الگوریتم طبقه بندی آنالیز تفکیک کننده خطی بیز جهت ارزیابی کیفیت مجموعه ژن انتخاب شده توسط آن ذره محاسبه می شود. الگوریتم پیشنهادی بر روی چهار مجموعه از پایگاه داده سرطان اعمال و نتایج آن با سایر روش های موجود مقایسه شده است. نتایج پیاده سازی نشان می دهد که الگوریتم پیشنهادی از دقت و اعتبار بالایی در مقایسه با سایر روش های موجود برخوردار بوده و قادر است یک مجموعه کوچک از ژن های حاوی اطلاعات را به گونه ای انتخاب کند که دقت طبقه بندی افزایش یابد.

کلیدواژه‌ها


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

Gene selection and cancer classification based on microarray data using combined BPSO and BLDA algorithm

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

  • M. joroughi 1
  • M. Shamsi 2
  • H.R. Saberkari 3
  • M.H. Sedaaghi 4
  • A. Momennezhad 3
1 Faculty of Electrical Engineering, Sahand University of Technology, Tabriz, Iran
2 Faculty of Electrical Engineering, Sahand University of Technology, Tabriz, Iran
3 Faculty of Electrical Engineering, Sahand University of Technology, Tabriz, Iran
4 Faculty of Electrical Engineering, Sahand University of Technology, Tabriz, Iran
چکیده [English]

Microarray data have an important role in identification and classification of the cancer tissues. In cancer researches always a few samples of microarrays are led to some problems in designing the classifiers, so non-informative genes have been removed from microarray data before classification using the preprocessing gene selection techniques. Basically, appropriate gene selection method can significantly improve the performance of cancer classification. In this paper, a new method is proposed based on hybrid model Binary Particle Swarm Optimization algorithm and Bayesian Linear Discriminant Analysis in order to classification of large scale microarray data. First, the position of each particle is represented in the form of binary vector and random, as each bit illustrates a gene. The zero and one bits represent that the corresponding feature (gene) is not/is selected, respectively. So the position of each particle clarifies a gene subset and fitness of each particle is calculated using Bayesian Linear Discriminant Analysis algorithm to quality evaluation of selected gene subset by that particle. The proposed algorithm is applied on four cancer datasets and its results are compared with other existed methods. Simulation results illustrate that proposed algorithm has high accuracy and validity compared to other existed methods and enables to select the small subset of informative genes in order to increase the classification accuracy.

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

  • Gene expression
  • Binary Particle Swarm Optimization
  • Bayesian Linear Discriminant Analysis
  • Classification
  • Gene selection

فناوری ریزآرایه[1] در سال 1996 متولد و با عناوین آرایه­های DNA[2]، تراشه­های ژنی، تراشه­های DNA و تراشه­های زیستی نامگذاری شده است. فناوری ریزآرایه یکی از آخرین پیشرفت­ها در زمینه زیست شناسی ملکولی است که اجازه نظارت بر بیان هزاران ژن را به­صورت همزمان تنها در یک آزمایش هیبریداسیون می­دهد. علاوه بر پتانسیل علمی این فناوری در مطالعه بنیادین بیان ژن؛ یعنی تنظیم و تعاملات ژن‌ها، کاربردهای مهمی در پژوهش­های دارویی و کلینیکی دارد. برای مثال، با مقایسه بیان ژن در سلول­های سالم و ناسالم، ریزآرایه می­تواند در شناسایی ژن‌های ناسالم برای داروهای درمانی یا ارزیابی تاثیر آن‌ها استفاده شود ]1[.

ریزآرایه دارای هزاران نقطه[3] بوده، هریک از این نقاط حاوی دنباله­های مختلف شناخته شده DNA، به­نام نشانگر[4] هستند. این نقاط روی یک اسلاید شیشه­ای توسط یک arrayer رباتیک چاپ می­شوند. دو نوع ریزآرایه بیشترین کاربرد را دارند: آرایه­های بر پایه DNA مکمل[5] وآرایه الیگو­نوکلئوتید که به اختصار الیگو نامیده می­شود ]1[. در حالت کلی، دو تفاوت عمده بین ریزآرایه cDNA و ریزآرایه الیگونوکلئوتید وجود دارد: اول اینکه در ریزآرایه cDNA  طول قطعه DNA بیشتر از طول قطعه DNA در ریزآرایه الیگونوکلئوتید است؛ دوم اینکه در آزمایش­های ریزآرایهcDNA  دو نمونه RNA، نمونه کنترل و نمونه تجربی، با دو فلورسنت مختلف (Cy3 و Cy5) علامت گذاری می­شوند ]3-1[. هدف از ریزآرایه cDNA مقایسه بیان ژن در دو نمونه مختلف است. شکل1 مراحل به‌دست آوردن داده­های ریزآرایه را نشان می­دهد. با توجه به این شکل می­توان مراحل به دست آوردن ریزآرایه DNA را به‌صورت زیر بیان کرد:

  • نمونه­گیری از نمونه­های مختلف( برای مثال نمونه­های سرطانی و سالم)؛
  • جداسازی mRNA از نمونه­ها و انجام رونویسی معکوس و تهیه cDNA؛
  • نشاندار کردن نمونه­های cDNA با رنگ‌های فلورسنت سبز و قرمز(Cy3 و Cy5)؛
  • ریختن نمونه­ها بر روی سطح اسلاید که از قبل توسط توالی­های ژن مورد نظر پوشیده شده است؛
  • شستن سطح اسلاید و
  • اسکن کردن آرایه هیبرید شده.

در ریزآرایه cDNA نمونه­های نشاندار شده با هم مخلوط می­شوند و سپس با مولکول­های DNA سطح اسلاید هیبرید می­شوند. هر چه جفت بازهای بیشتری با هم مکمل شوند، پیوند هیدروژنی قویتری تشکیل می­شود. بعد از هیبرید شدن نمونه­های نشاندار شده با مولکول­های DNA سطح اسلاید، اسلاید شسته می­شود. بر اثر شستشو پیوندهای ضعیفـتر از بین می­روند و پیوندهای قویتر باقی می­مانند. میزان شدت و قدرت سیگنال نهایی وابسته به میزان نمونه­هایی است که با توالی­های روی سطح، اتصال قوی برقرار کرده­اند.

داده­های ریزآرایه به­صورت ماتریسی از هزاران ستون و چند صد سطر هستند که هر سطر نشان­دهنده یک نمونه و هر ستون نیز نشان­دهنده یک ژن است. ابعاد بالای ویژگی­ها و تعداد نسبتاً کم نمونه­ها باعث ایجاد مشکلاتی در آنالیز داده­های ریزآرایه شده است .این مشکلات عبارتند از ]4و5[:

  • افزایش هزینه محاسباتی و پیچیدگی طبقه­بندها؛
  • کاهش توانایی تعمیم طبقه­بندها و کاهش اعتبار آن­ها در پیش­بینی نمونه­های جدید؛
  • به ­علت بالا بودن تعداد ویژگی­ها نسبت به نمونه‌ها، احتمال آنکه ژن­های نامربوط خود را در هنگام یافتن ژن­های با بیان مختلف و در ساختن مدل­های پیش‌بینی­کننده نشان دهند، بسیار زیاد است و
  • تفسیر ژن­های مسبب بیماری مشکل است؛ زیرا از دیدگاه بیولوژیکی تنها مجموعه کوچکی از ژن­ها مربوط به بیماری هستند. در نتیجه، داده­های مربوط به اکثریت ژن­ها در واقع نقش یک پس­زمینه نویزی را دارند که می­تواند اثر آن زیرمجموعه کوچک را محو کند. بنابراین، تمرکز بر روی مجموعه کوچکتری از داده­های بیان ژن، باعث تفسیر بهتر نقش ژن­های حاوی اطلاعات می شوند.

از این­رو، اولین قدم مهم در آنالیز داده­های ریزآرایه کاهش تعداد ژن­ها یا به عبارتی، انتخاب ژن­های متمایزکننده به­منظور طبقه­بندی است. در این مقاله یک الگوریتم بهینه بر مبنای مدل ترکیبی بهینه­سازی ازدحام ذرات باینری[6] و آنالیز تفکیک­کننده خطی بیز[7] برای این­منظور ارائه شده است. استفاده از این الگوریتم به کاهش نویز موجود در داده­های ریزآرایه و همچنین، افزایش صحت طبقه­بندی آن­ها منجر می­شود. در ادامه، در بخش2 پایگاه­های داده ریزآرایه استفاده شده معرفی می­شود. در بخش3، فرآیند کلی استخراج ویژگی و طبقه­بندی داده­های ریزآرایه مطرح و مراحل مختلف آن توضیح داده می­شود. در بخش4 مدل ترکیبی پیشنهاد شده بر پایه الگوریتم ترکیبی بهینه­سازی ازدحام ذرات باینری و آنالیز تفکیک­کننده خطی بیز معرفی و مراحل مختلف آن به تفصیل بیان می­شود. نتایج پیاده­سازی بر روی چهار پایگاه داده در بخش5 مطرح شده و نهایتا بخش6 شامل نتیجه­گیری و جمع­بندی است.

 

 

 

 

شکل (1): مراحل مختلف به‌دست آوردن داده‌های ریزآرایه]1[

 

 

1- پایگاه‌های داده

در این مقاله از چهار پایگاه داده ریزآرایه استفاده شده که در ادامه به توضیح آن­ها می­پردازیم. شایان ذکر است که تمامی نمونه­ها با به­کارگیری آرایه­های الیگو نوکلئوتیدی با چگالی بالا اندازه­گیری شده­اند ]6[ . داده­های استفاده شده در این مقاله از مرجع ]7[ استخراج شده است.

سرطان خون: این پایگاه داده شامل 72 نمونه از آزمایش های ریزآرایه با 7129 سطوح بیان ژن است. مساله اصلی در آن جداسازی دو نوع از داده­های سرطان خون، ALL[8] و AML[9] است. داده­ها به دو دسته 34 نمونه کنترل (20 مورد مربوط به ALL و 14 مورد مربوط به AML) که در فرآیند تست استفاده شده و 38 نمونه سرطانی (27 مورد مربوط به ALL و 11 مورد مربوط به AML) استفاده شده در فرآیند آموزش، تقسیم می­شوند.

سرطان پستان: این پایگاه داده شامل 97 نمونه از آزمایش های ریزآرایه با 24481 سطوح بیان ژن است. داده‌ها به دو دسته 19 نمونه کنترل (12 مورد مربوط به نمونه‌های عود کرده[10] و 7 مورد مربوط به نمونه­های عود نکرده[11]) که در فرآیند تست استفاده شده و 78 نمونه (34 مورد مربوط به نمونه­های عود کرده و 44 مورد مربوط به نمونه­های عود نکرده) استفاده شده در فرآیند آموزش، تقسیم می­شوند.

سرطان ریه: این پایگاه داده شامل 181 نمونه از آزمایش های ریزآرایه با 12533 سطوح بیان ژن است. داده­ها به دو دسته 149 نمونه کنترل (15 مورد مربوط به نمونه­های  [12]MPM و 134 مورد مربوط به نمونه­های [13]ADCA که در فرآیند تست استفاده شده و 32 نمونه (16 مورد مربوط به نمونه­های MPM و 16مورد مربوط به نمونه­های  ADCA استفاده شده در فرآیند آموزش، تقسیم می­شوند.

سرطان پروستات: این پایگاه داده شامل 136 نمونه از آزمایش های ریزآرایه با 12600 سطوح بیان ژن است. داده‌ها به دو دسته 34 نمونه کنترل (25 مورد مربوط به نمونه‌های تومور و 9 مورد مربوط به نمونه­های بدون تومور) که در فرآیند تست استفاده شده و 102 نمونه (52 مورد مربوط به نمونه­های تومور و 50 مورد مربوط به نمونه­های نرمال) استفاده شده در فرآیند آموزش، تقسیم می­شوند.

 

2- فرآیند کلی استخراج ویژگی و طبقه­بندی داده­های ریزآرایه

یکی از مسائل مهم در تحلیل داده­های ریزآرایه انتخاب ژن است و آن فرآیندی است که تعداد کمی از ژن­ها قبل از طبقه­بندی انتخاب می­شوند. ابعاد بالا، تعداد نسبتا کم نمونه‌ها و تغییرپذیری ذاتی در فرآیندهای آزمایشگاهی و بیولوژیکی باعث ایجاد مشکلاتی در آنالیز داده­های ریزآرایه شده است. از این­رو، اولین گام مهم در آنالیز داده­های ریزآرایه کاهش تعداد ژن­ها یا به عبارتی انتخاب ژن­های متمایزکننده به­منظور طبقه­بندی است. این مرحله انتخاب ژن نامیده می­شود. شکل2 مراحل کلی استخراج ویژگی و طبقه‌بندی داده­های ریزآرایه را نشان می­دهد. این مراحل در حالت کلی به­صورت زیر هستند که در ادامه با جزئیات کامل مطرح می­شوند:

  • پیش‌پردازش داده‌های بیان ژن؛
  • انتخاب یک مجموعه ژن­های حاوی اطلاعات؛
  • طبقه­بندی داده­ها و
  • ارزیابی و اعتبارسنجی نتایج حاصل شده.

 

2-1- پیش‌پردازش داده‌های بیان ژن

پیش از اعمال الگوریتم­های استخراج ویژگی و طبقه‌بندی نیاز است که داده مورد استفاده پیش­پردازش شود. داده­های مورد استفاده در این مقاله با به­کارگیری نرم­افزار Weka فراخوانی شده که دارای فرمت ARFF[14] هستند. به­علت تغییرات زیاد داده، گسسته­سازی مقادیر آن برای دستیابی به صحت طبقه­بندی مناسب ضروری است. گسسته­سازی فرآیند تبدیل ویژگی­ها و متغیرهای پیوسته به مقادیر و یا ویژگی­های گسسته است. معمولا طی این فرآیند، داده­ها به k بخش با طول یکسان (بازه­های یکسان) و یا k% از کل داده (فرکانس­های یکسان) گسسته می­شوند.

 

2-2- انتخاب مجموعه ژن‌های حاوی اطلاعات برای طبقه‌بندی داده‌های ریزآرایه

پژوهش ها نشان داده که تشخیص دقیق سرطان می‌تواند با طبقه­بندی داده­های ریزآرایه عملی شود. با وجود این، مشکل اصلی در تحلیل­ داده­های ریزآرایه بعد بالای آن‌هاست که در نتیجه تعداد بسیار زیاد متغیرها (ژن­ها) در مقابل تعداد کم نمونه­ها ایجاد می­شود. اگرچه تعداد بسیار زیادی از ژن در داده­های ریزآرایه وجود دارند، تنها بخش اندکی از آن­ها تاثیر بسزایی در صحت طبقه­بندی می­گذارند. بسیاری از ژن­ها عملکرد مشابهی در دو حالت نرمال و غیرنرمال (سرطانی) دارند. همچنین، برخی از ژن­ها به‌صورت نویز در داده­ها ظاهر می­شوند. وجود ژن­های حاوی نویز در بروز سرطان نقشی نداشته، اثر منفی در صحت طبقه­بندی می­گذارند. بنابراین، داده­های ریزآرایه قبل از طبقه­بندی از طریق تکنیک­های انتخاب ژن پیش­پردازش و ژن­های فاقد اطلاعات آن­ها دور ریخته می­شود. انجام این‌کار باعث افزایش بازدهی طبقه­بندی­کننده و همچنین، کاهش پیچیدگی محاسباتی خواهد شد ]8[.

به­طور کلی، می­توان گفت سه مدل انتخاب ویژگی (ژن) وجود دارد ]9[. مدل اول مدل فیلتر است که عمل انتخاب ویژگی و طبقه­بندی را در دو مرحله جداگانه انجام می­دهد. این مدل ژن­هایی را به عنوان ژن­های مؤثر انتخاب می­کند که دارای توانایی تفکیک­کنندگی بالایی باشند. این مدل مستقل از طبقه­بندی یا الگوریتم یادگیری است و از لحاظ محاسبات ساده و سریع است. مدل دوم مدل wrapper است که انتخاب ویژگی و طبقه­بندی را در یک فرآیند انجام می‌دهد. این مدل در حین فرآیند جست‌وجوی ژن‌های مؤثر، از طبقه­بند استفاده می­کند. به عبارتی، مدل wrapper از یک الگوریتم یادگیری برای تست زیر مجموعه ژن انتخاب شده استفاده می­کند. صحت مدل wrapper نسبت به مدل فیلتر بیشتر است. روش­های مختلفی برای انتخاب زیرمجموعه­های مناسب بر مبنای مدل wrapper در مقالات ارائه شده است. در ]10[ از الگوریتم­های تکاملی همراه با طبقه­بند K نزدیکترین همسایگی برای این منظور استفاده شده است. در ]11[ الگوریتم­های ژنتیک موازی با به‌کارگیری عملگرهای تطبیقی گسترش یافته است. همچنین در ]12[ از مدل ترکیبی الگوریتم ژنتیک و ماشین بردار پشتیبان برای انتخاب یک مجموعه از ژن­ها و طبقه­بندی آن‌ها استفاده شده است. در ]13[ نیز مساله انتخاب و طبقه‌بندی ژن به­صورت یک مساله بهینه­سازی چند مرحله­ای مطرح شده که در آن به­طور همزمان تعداد ویژگی­ها (ژن­ها) و همچنین تعداد نمونه­های اشتباه طبقه‌بندی شده کاهش داده می­شود.

نهایتا در مدل­های ترکیبی، فرآیند انتخاب یک مجموعه از ژن­های مؤثر در حین فرآیند آموزش توسط یک طبقه­بند خاص صورت می­گیرد. یک نمونه از این روش، استفاده از ماشین بردار پشتیبان به­همراه حذف ویژگی­های بازگشتی است. ایده این روش، حذف یک به یک ژن­ها و بررسی اثر حذف شدن آن­ها در خطای مورد انتظار است ]14[. الگوریتم حذف ویژگی­های بازگشتی یک روش رتبه­بندی ویژگی رو به عقب است؛ به عبارتی آن دسته از ژن­هایی که در آخرین مرحله حذف می­شوند، بهترین نتیجه طبقه­بندی را به­دست می­دهند، در حالی­که این ژن­ها ممکن است به­تنهایی همبستگی خوبی با کلاس­ها نداشته باشند. مدل­های ترکیبی را می­توان حالت تعمیم یافته مدل wrapper در نظر گرفت. دو نمونه دیگر از مدل ترکیبی در ]15[ و ]16[ اشاره شده است.

 

 

 

 

خیر

بلی

تعداد نمونه­های درست طبقه­بندی شده

مدل­های طبقه­بندی

داده­های پیش­پردازش شده حاوی سطوح  بیان ژن

انتخاب ژن­های مؤثر با به­کارگیری الگوریتم­های استخراج ژن

مجموعه ژن­های حاوی اطلاعات

مجموعه آموزشی

مجموعه تست

آموزش نمونه­ها با به­کارگیری الگوریتم­های طبقه­بندی

تعداد نمونه­های درست طبقه­بندی شده

مطابقت با خروجی مطلوب دارد؟

شکل (2):بلوک دیاگرام مراحل مختلف تحلیل داده­های ریزآرایه

 

2-3- ارزیابی و اعتبار سنجی نتایج

آخرین گام در تحلیل داده­های ریزآرایه ارزیابی نتایج حاصل از اعمال الگوریتم­های طبقه­بندی است. در این مقاله ارزیابی نتایج بر اساس روش اعتبارسنجی k-fold انجام گرفته که در آن k اشاره به تعداد دفعات تکرار داشته و مقدار آن برابر 10 در نظر گرفته شده است. از این­رو اعتبارسنجی fold-10 به این ترتیب صورت می­گیرد که ابتدا نمونه­ها به 10 بخش تقسیم شده و در هر بار اجرای الگوریتم، 1/0 کل داده­ها به­عنوان نمونه­های تست و باقیمانده آن­ها به­عنوان نمونه­های آموزشی در نظر گرفته می­شود. این روند 10 بار با به­کارگیری داده­های آموزشی و تست مختلف انجام گرفته و نتیجه با گرفتن مقدار متوسط در 10 بار تکرار آزمایش به­دست می­آید.

 

3- مدل پیشنهاد شده بر پایه الگوریتم ترکیبی BPSO و BLDA

مدل پیشنهاد شده بر پایه آنالیز همبستگی پیرسون، الگوریتم بهینه­سازی ازدحام ذرات باینری و آنالیز تفکیک­کننده خطی بیز است. شکل(3) بلوک دیاگرام الگوریتم پیشنهادی را نشان می­دهد. گام­های اصلی این الگوریتم به صورت زیر هستند که در ادامه با جزئیات کامل مطرح می‌شوند:

  • پیش­پردازش داده­ها و انتخاب مجموعه ای از ژن­ها با استفاده از آنالیز همبستگی پیرسون؛
  • استفاده از الگوریتم ترکیبی BPSO/BLDA برای انتخاب مجموعه ژن­های حاوی اطلاعات و طبقه­بندی آن­ها.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


شکل (3): بلوک دیاگرام الگوریتم پیشنهادی

 

 

 

3-1- پیش‌پردازش داده‌ها و انتخاب مجموعه­ای از ژن‌ها با استفاده از آنالیز همبستگی پیرسون[15]

به‌منظور امتیازدهی به هر ژن، دو نشا‌نگر ویژگی ایده‌آل باینری مطابق رابطه (1) تعریف می‌شود. اولین نشانگر در کلاس A دارای مقدار یک و در کلاس B دارای مقدار صفر است و دومین نشانگر در کلاس A دارای مقدار صفر و در کلاس B دارای مقدار یک است.

(1)

 

اگر ژن­ها مشابه نشانگرها باشند یا به­عبارتی فاصله بین ژن­ها و نشانگرها کوچک باشد، آنگاه این ژن­ها به­عنوان ژن­های حاوی اطلاعات برای طبقه­بندی انتخاب می­شوند. در این مقاله برای محاسبه فاصله هر ژن از نشانگرها از معیار آنالیز همبستگی پیرسون استفاده شده که به­صورت زیر تعریف می­شود]8[:

 

(2)

 

که در آن n تعداد نمونه­های آموزشی،  میانگین ژن،  میانگین نشانگر ایده­آل،  i امین مقدار از بردار ژن و  i امین مقدار باینری از بردار نشانگر ایده­آل است. به­منظور پیش­پردازش اولیه، معیار PC برای تمامی ژن­ها محاسبه شده و k ژن که دارای PC کوچکتری هستند به­عنوان ژن­های حاوی اطلاعات اولیه انتخاب می­شوند.

 

3-2- الگوریتم بهینه­سازی ازدحام ذرات باینری

ایده بهینه­سازی ازدحام ذرات برای اولین بار توسط کندی و ابرهارت در سال 1995 مطرح شد ]17[. PSO یک الگوریتم محاسبه­ای تکاملی الهام گرفته از طبیعت و براساس تکرار است. منبع الهام این الگوریتم رفتار اجتماعی حیوانات، همانند حرکت دسته جمعی پرندگان و ماهی­ها بوده است. در این الگوریتم هر پاسخ مساله به­صورت یک ذره مدل می­شود. هر ذره برای به­دست آوردن بهترین پاسخ مساله از تجربه خود و از تجربیات به­دست آمده از جمعیت استفاده می­کند. الگوریتم PSO از تعداد مشخصی از ذرات تشکیل می­شود. برای هر ذره دو مقدار موقعیت و سرعت تعریف می­شود که به­ترتیب با یک بردار مکان و یک بردار سرعت مدل می­شوند. یک حافظه به ذخیره بهترین موقعیت هر ذره در گذشته و یک حافظه نیز به ذخیره بهترین موقعیت پیش آمده در میان همۀ ذرات اختصاص می­یابد. با تجربه حاصل از این حافظه­ها، ذرات تصمیم می­گیرند که در نوبت بعدی چگونه حرکت کنند. در طول حرکت،  هر ذره موقعیت خود را با تغییر سرعت با توجه به بهترین موقعیت خود و بهترین موقعیت پیش آمده در بین همه ذرات تنظیم می­کند. بنابراین، حرکت هر ذره به سه عامل بستگی دارد: موقعیت فعلی ذره، بهترین موقعیتی که ذره تاکنون داشته است(Pbest) و بهترین موقعیتی که کل مجموعه ذرات تاکنون داشته­اند(Gbest) ]17[. PSO به طور موفقیت آمیزی در زمینه­های بهینه­سازی توابع، فرایند آموزش شبکه‌های عصبی، سیستم­های کنترل فازی و غیره استفاده شده است. کندی و ابرهات در سال 1997 نوع باینری الگوریتم PSO را نیز معرفی کردند که در موارد متغیرهای گسسته باینری استفاده می­شود. در BPSO موقعیت هر ذره به‌صورت بردار باینری صفر و یک تعریف می­شود و سرعت هر ذره به‌صورت تعداد بیت­های تغییر یافته در هر تکرار تعبیر می‌شود ]18[.

 

3-3- الگوریتم آنالیز تفکیک کننده خطی بیز

الگوریتم BLDA یک الگوریتم قابل تنظیم بوده که به‌منظور جلوگیری از بیش برازش[16] در داده­های با ابعاد بالا به‌کار می‌رود. با استفاده از این الگوریتم درجه تنظیم می‌تواند به­صورت اتوماتیک و به­سرعت از طریق داده­های آموزشی و بدون نیاز به استفاده از اعتبارسنجی تخمین زده شود. این طبقه­بند برای طبقه­بندی داده­های حاوی نویز و همچنین، ویژگی­هایی که به­طور دقیق قابل طبقه­بندی نیستند استفاده می­شود ]19[ . اساس این طبقه­بند بدین صورت است که در آن رگرسیون در چارچوب بیز صورت می­گیرد ]20[. بدین صورت، هدف­ها و بردار ویژگی یک رابطه خطی با یکدیگر خواهند داشت. این رابطه به­صورت زیر است:

(3)

 

که در آن t و x به­ترتیب بردار هدف و ویژگی، w بردار وزن ( ) و n نویز سفید است. در این­ صورت تابع همانندی برای وزن­های w استفاده شده در رگرسیون به‌صورت زیر بیان می­شود:

(4)

 

که در آن X ( ) ماتریس سطری حاوی بردارهای ویژگی، D نشان­دهنده دو پارامتر ،  معکوس واریانس و N نشان­دهنده تعداد نمونه­ها در مجموعه آموزشی است. به­منظور توصیف یک مجموعه بیز باید توزیع پیشین برای بردارهای وزن تعیین شود. این توزیع اطلاعات اولیه­ای درباره بردار وزن به­دست داده و به‌صورت زیر تعریف می­شود:

(5)

 

که در آن  نشان­دهنده معکوس واریانس توزیع اولیه برای بردارهای وزن ،  یک ماتریسی قطری مربعی با ابعاد 1+D بوده که D تعداد ویژگی است. با داشتن توزیع پیشین و تابع همانندی می­توان توزیع پسین را با به‌کارگیری قانون بیز به­صورت زیر به­دست آورد:

(6)

 

 

از آنجا که توزیع پیشین و تابع همانندی، گوسی هستند توزیع پسین نیز گوسی خواهد بود. بنابراین، میانگین و کوواریانس این توزیع به­صورت زیر است:

(7)

 

از این­رو، توزیع پسین می­تواند برای محاسبه احتمال توزیع اهداف رگرسیون، ، برای بردار ویژگی جدید  استفاده شود. در این صورت، توزیع پیش­بینی­کننده به‌صورت زیر نشان داده می­شود:

(8)

 

 

توزیع بیان شده در رابطه (8) یک توزیع گوسی با میانگین و واریانس  است که برای بردار ورودی جدید ، مقادیر مختلف  را تعیین می­کند.شایان ذکر است که در الگوریتم BLDA هدف­های رگرسیون برای نمونه­های کلاس1 در  و برای نمونه­های کلاس2 در   تنظیم می­شوند که در آن N تعداد کل نمونه­های آموزشی،  تعداد نمونه­های کلاس1 و تعداد نمونه­های کلاس2 است ]21[. از این­رو، احتمال نمونه­های کلاس1 به­صورت زیر به­دست می­آید:

(9)

 

 

3-4- انتخاب ویژگی و طبقه­بندی با استفاده از مدل ترکیبی BPSO/BLDA

در این مقاله از الگوریتم BPSO برای اجرای فرآیند انتخاب ژن و از الگوریتم BLDA به­عنوان ارزیابی­کننده برای طبقه­بندی به­دست آمده توسط BPSO استفاده شده است. روش کار بدین صورت است که الگوریتم BPSO از 30 ذره و هر ذره نیز از 70 بیت باینری تشکیل شده است. موقعیت هر ذره توسط این 70 بیت باینری تعریف می­شود. هر بیت نشان­دهنده یک ژن است؛ به­طوری­که بیت صفر نشان­دهنده این است که ویژگی (ژن) متناظر با آن انتخاب نشده و بیت یک نیز نشان­دهنده این است که ویژگی (ژن) متناظر با آن انتخاب شده است. شکل4 نمایشی از ازدحام ذرات را نشان می­دهد. ذرات بعد از هر بار به روز رسانی ارزیابی می­شوند. موقعیت هر ذره بیانگر یک مجموعه ژن است؛ لذا میزان تناسب هر ذره توسط طبقه­بند BLDA برای ارزیابی کیفیت مجموعه ژن انتخاب شده توسط آن ذره محاسبه می­شود. بهترین میزان تناسب هر ذره pbest و بهترین میزان تناسب در میان گروه ذرات gbest نامیده می‌شود. این فرآیند تا زمانی­ که معیار توقف برآورده نشود تکرار خواهد شد. معیار توقف می­تواند بیشترین تعداد تکرار و یا میزان تناسب بیشینه تعریف شود ]22[. سرعت ذرات در الگوریتم BPSO توسط رابطه زیر به روز رسانی می­شود:

 

(10)

 

 

اگر  در بازه  نباشد، آنگاه سرعت ذرات در الگوریتم PSO باینری به­صورت زیر تعیین می­شود:

 

(11)

 

برای تبدیل بردار سرعت به بردار احتمال از تابع تبدیل سیگموئید به­صورت زیر استفاده می­کنیم:

 

(12)

 

از این­رو، با به­کارگیری رابطه (12) موقعیت ذرات نیز به­صورت زیر به روز رسانی می­شود:

 

(13)

 

 

در روابط فوق  وزن اینرسی، d بعد مساله،  و  فاکتورهای شتاب و  ،   و   اعداد تصادفی در بازه ]1و0[ هستند. همچنین  سرعت ذره در مرحله جدید و   سرعت در مرحله قبلی و   موقعیت قبلی ذره است. الگوریتم BPSO به­صورت زیر خلاصه می­شود:

 

 

الگوریتم BPSO

شروع

تولید ذرات اولیه به­صورت تصادفی

تازمانی که معیار توقف برآورده شود، مراحل زیر تکرار می‌شوند:

 

ارزیابی میزان تناسب ذرات توسط طبقه­بند BLDA

برای p =1:N (N تعداد ذرات)

 

اگر (میزان تناسب ) > (میزان تناسب ) آنگاه

 

پایان

 

اگر (میزان تناسب یکی از ها) > (میزان تناسب ) آنگاه

موقعیت آن ذره

پایان

 

برای  (D: تعداد ابعاد ذرات)

 

اگر  در بازه  نباشد آنگاه:

 

 

استفاده از تابع تبدیل سیگموئید تبدیل بردار سرعت به بردار احتمال

 

 

اگر  آنگاه . در غیراینصورت

 

تکرار مراحل فوق تا برآورده شدن معیار توقف.

پایان

 

شکل (4): نمایش ازدحام ذرات در الگوریتم BPSO

 

 

4- نتایج پیاده­سازی

کلیه مراحل پیاده­سازی الگوریتم­ پیشنهادی بر روی یک کامپیوتر با پردازنده GHz4/3 و حافظه RAM برابر GHz1 انجام گرفته است. مقادیر پارامترهای استفاده شده درالگوریتم BPSO در جدول1 نشان داده شده است.

در جدول2 نتایج به­دست آمده از صحت الگوریتم پیشنهادی با اعمال روش اعتبارسنجی fold-10 و همچنین میانگین صحت در چهار پایگاه داده نشان داده شده است. در این جدول، Acc (٪) و Avg (N) به­ترتیب نشان­دهنده صحت در 10 بار اجرای الگوریتم و میانگین تعداد ژن­های انتخاب شده در هر بار اجرای الگوریتم است. همان­طور که مشاهده می­شود، بیشترین صحت طبقه­بندی در پایگاه داده سرطان خون برابر 39/92 بوده هنگامی که میانگین تعداد ژن­های انتخاب شده برابر 48 است. کمترین صحت طبقه‌بندی در این پایگاه داده نیز برابر 47/85 است که در این­حالت 67 ژن انتخاب شده است. به­طور مشابه، بیشترین صحت طبقه­بندی در پایگاه­های داده ریه، پستان و پروستات به­ترتیب 66/99، 63/94 و 68/96 است که میانگین تعداد ژن­های انتخاب شده در آن­ها به­ترتیب 39، 43 و 50 است. کمترین مقدار صحت طبقه­بندی در این پایگاه­های داده نیز به­ترتیب برابر 26/96، 78/90 و 05/94 است که در این‌حالت میانگین تعداد ژن­های انتخاب شده به­ترتیب برابر 38، 38 و 40 است. در شکل5 نیز میانگین صحت طبقه­بندی الگوریتم پیشنهادی در 10 بار اجرای آن در چهار پایگاه داده به­طور شهودی نشان داده شده است.

 

 

 

 

 

جدول (1): مقادیر پارامترهای به­کار رفته در الگوریتم BPSO

مقادیر پارامترهای استفاده شده در الگوریتم PSO باینری

m: تعداد ذرات

30

C1 , C2: فاکتورهای شتاب

2

Vmax: بیشینه سرعت ذرات

6

Vmin: کمینه سرعت ذرات

6-

R1 , R2: اعداد تصادفی

]1و0[

N: طول هر ذره(تعداد بیت)

70

Max iter: بیشینه تکرار

50

w: وزن اینرسی

 

Wmax: بیشینه وزن اینرسی

995/0

Wmin: کمینه وزن اینرسی

5/0

 

 

پایگاه­های داده

تعداد اجرای الگوریتم

جدول (2): مقادیر کمّی صحت به­دست آمده از اعمال الگوریتم پیشنهادی در 10 بار اجرای الگوریتم بر روی چهار پایگاه داده

 

 

 

سرطان خون

 

 

سرطان ریه

 

 

سرطان پستان

 

 

سرطان پروستات

 

 

 

 

 

 

 

 

 

 

ACC

 (%)

Avg

ACC (%)

 Avg

ACC (%)

Avg

ACC (%)

Avg

1

57/90

42

63/99

40

41/94

43

56/94

54

2

39/92

48

33/99

40

75/93

24

52/95

52

3

64/89

48

26/99

50

52/94

41

83/95

45

4

47/85

67

56/99

39

15/92

34

63/99

50

5

21/89

47

26/96

38

63/94

43

68/96

50

6

64/86

45

33/99

40

32/92

29

19/96

40

7

56/87

39

33/99

40

41/94

48

05/94

40

8

62/87

37

28/99

53

41/94

42

12/94

40

9

11/88

65

37/99

40

77/91

34

56/96

57

10

99/87

62

66/99

39

78/90

38

25/96

45

میانگین

53/88

50

43/99

42

31/93

38

93/95

47

 

 

شکل (5): ترسیم منحنی میانگین صحت طبقه­بندی الگوریتم پیشنهادی در 10 بار اجرای آن بر روی چهار پایگاه داده

 

 

در جدول3 مقایسه الگوریتم پیشنهادی با سایر روش‌های موجود در مراجع از نظر صحت طبقه­بندی در پایگاه داده سرطان خون نشان داده شده است. همان­طور که مشاهده می­شود، میزان بهبود صحت طبقه­بندی در الگوریتم پیشنهادی نسبت به روش­های PSO+ANN ]23[، Nero-Fuzzy ]24[ و KNN ]25[ به­ترتیب به­میزان 8/2،  2/1 و 9/21 درصد است. صحت الگوریتم پیشنهادی تنها از الگوریتم طبقه­بند Bayesian ]26[ پایین­تر است. به­طور مشابه، عملکرد الگوریتم پیشنهادی با سایر روش­ها در پایگاه داده سرطان ریه مقایسه شده و در جدول4  نشان داده شده است. بر اساس این جدول، صحت طبقه­بندی در الگوریتم پیشنهادی نسبت به روش­های PSO+SVM ]27[، IPSO+KNN ]28[، PSO+ANN و Bayesian به­ترتیب به­میزان 4/0، 9/2، 1/1 و 7/11 درصد بهبود می­یابد. صحت طبقه­بندی الگوریتم پیشنهادی در این پایگاه داده تنها از روش ترکیبی PSO+ Ensemble NN ]23[ کمتر است. عملکرد الگوریتم پیشنهادی با روش­های PSO+SVM،  GA+SVM ]27[ و ‌Bayesian در پایگاه داده سرطان پستان نیز مقایسه شده که در جدول5 نشان داده شده است. برتری الگوریتم پیشنهادی نسبت به دو روش PSO+SVM و Bayesian به­وضوح در این جدول مشاهده می­شود؛ به­طوری­که میزان بهبود در الگوریتم پیشنهادی به­ترتیب برابر 4/9 و 1/26 درصد است. نهایتا الگوریتم پیشنهادی با روش­های IPSO+KNN، الگوریتم ترکیبی PSO/GA+SVM ]29[ و KNN+EA ]30[ اعمال شده

 

بر پایگاه داده سرطان پروستات مقایسه و در جدول6 نشان داده شده است. برتری الگوریتم پیشنهادی نسبت به همه روش­های مطرح شده در این جدول مشاهده می­شود؛ به‌طوریکه میزان بهبود صحت به‌ترتیب برابر 1/4، 7/2 و 9/7 درصد است.

دلیل برتری الگوریتم پیشنهادی را می­توان از دو لحاظ انتخاب ویژگی و روش طبقه­بندی بررسی نمود. BPSO شباهت زیادی با الگوریتم­های محاسبه­ای تکاملی مانند الگوریتم ژنتیک دارد. BPSO بر اساس رفتار اجتماعی در جمعیت­های بیولوژیکی است. الگوریتم­های BPSO و ژنتیک روش­های جستجوی مبتنی بر جمعیت هستند که با اشتراک گذاری اطلاعات میان اعضای خود و با استفاده از قوانین قطعی و احتمالی، فرآیند جستجو را بهبود می­بخشند. با این حال BPSO اپراتورهای ژنتیک مانند اپراتورهای تقاطع و جهش را ندارد. البته، مدل اجتماعی تعامل بین ذرات را می­توان شبیه اپراتور تقاطع در نظر گرفت. برای مثال، پارامترهای rand1 و rand2 (رابطه 10) که بر سرعت ذرات اثر می­گذارند، شبیه پارامتر جهش در الگوریتم ژنتیک هستند. در حقیقت، تنها تفاوت بین آن­ها این است که اپراتورهای تقاطع و جهش در الگوریتم ژنتیک احتمالاتی است، در حالی­که ذرات جدید در BPSO باید در هر تکرار بدون هیچ احتمالی پردازش شوند. در مقایسه با الگوریتم ژنتیک، مکانیسم به اشتراک گذاری اطلاعات در BPSO به‌طور قابل توجهی متفاوت است. در الگوریتم ژنتیک سیر تکاملی با استفاده از اپراتورهای تقاطع و جهش انجام می‌شود. کروموزوم­ها اطلاعات را بین یکدیگر به اشتراک گذاشته، کل جمعیت همانند یک گروه به سمت منطقه هدف حرکت می­کنند. در فضای مساله، این مدل شبیه به جستجوی فقط یک ناحیه است. بنابراین، نقطه ضعف این مدل این است که به راحتی می­تواند در بهینه­های محلی گیر کند، اما در BPSO هر ذره در فضای مساله به­صورت یکنواخت توزیع شده­ و  فقط gbest اطلاعات را برای سایر ذرات فراهم می­کند. این یک مکانیسم به اشتراک­گذاری یک­طرفه است و سیر تکاملی فقط در جهت بهترین راه حل است. عملکرد BPSO تحت تاثیر پارامترهای w و فاکتورهای شتاب c1 و c2 است. با مقداردهی مناسب این پارامترها (جدول 1) به­راحتی می­توان به نتایج مطلوب دست یافت. اگر مقادیر این پارامترها خیلی کوچک انتخاب شود، حرکت ذرات نیز خیلی آهسته و زمان­بر خواهد بود و اگر مقادیر پارامترها بزرگ انتخاب شود، الگوریتم تضعیف شده و مجموعه ویژگی­های مفید به دست نمی­آید. بنابراین، تنظیم مناسب پارامترها، الگوریتم BPSO را به­راحتی قادر به انتخاب ویژگی­های مهم می­کند.

در مورد روش انتخاب طبقه­بندی نیز می­توان این­گونه توضیح داد که اگرچه SVM در طبقه­بندی تومور در اغلب موارد به­­خوبی عمل می­کند، ولی پیچیدگی محاسباتی بالایی در یافتن بهترین ترکیب پارامترها دارد]31[. اما طبقه­بند BLDA به­راحتی و با صرف زمان کم قابل پیاده­سازی است. همان­طور که در جدول­های 3 الی 6 مشاهده می­شود، ترکیب روش انتخاب ژن BPSO و طبقه­بند BLDA در اغلب موارد دارای نتیجه بهتری است.

همان­طور که از شکل­های6 (الف) تا (د) مشاهده می‌شود، الگوریتم پیشنهادی به­خوبی قادر به جداسازی سطوح بیان ژن­ها به دو کلاس است. برای مثال در داده سرطان خون (شکل6 (الف))، تعداد 27 نمونه مربوط به کلاس ALL و 11 نمونه مربوط به کلاس AML است که این تفکیک به­خوبی در این شکل نشان داده شده است. به‌طور مشابه، در داده سرطان پستان نیز تعداد 34 نمونه مربوط به نمونه­هایی است که در آن­ها سرطان عود کرده و 44 نمونه نیز به نمونه­هایی مرتبط است که سرطان در آن­ها عود نکرده است. این تفکیک نیز در شکل6 (ب) مشاهده می­شود. در داده­های سرطان ریه و پروستات نیز وضعیت مشابهی مشاهده می­شود؛ به­طوری­که در داده­های سرطان ریه تعداد 16 نمونه مربوط به نمونه­های MPM و 16 نمونه نیز مربوط به ADCA است و این تفکیک در شکل6 (ج) نشان داده شده است. نهایتا در داده­های سرطان پروستات نیز تعداد 52 نمونه مربوط به نمونه­های تومور و 50 نمونه نیز مربوط به نمونه­های بدون تومور است و این تفکیک نیز در شکل6 (د) به­خوبی انجام گرفته است. در جداول 7 تا 10 نیز شماره ژن­های مؤثر به­دست آمده از اعمال الگوریتم پیشنهادی آورده شده است.

 

جدول (3): مقایسه نتایج کمّی صحت طبقه‌بندی در الگوریتم پیشنهادی و سایر روش‌ها در پایگاه داده سرطان خون

الگوریتم انتخاب ژن

طبقه­بند

صحت طبقه­بندی (٪)

BPSO

BLDA

5/88

PSO

ANN

1/86

-

Nero-Fuzzy

5/87

-

KNN

6/72

-

Bayesian

2/91

 

 

 

جدول (4): مقایسه نتایج کمّی صحت طبقه­بندی در الگوریتم پیشنهادی و سایر روش­ها در پایگاه داده سرطان ریه


الگوریتم انتخاب ژن

طبقه­بند

صحت طبقه­بندی (٪)

BPSO

BLDA

5/99

PSO

SVM

0/99

IPSO

KNN

5/96

PSO

Ensemble Neural Network

100

PSO

ANN

3/98

-

Bayesian

4/89

 

جدول (5): مقایسه نتایج کمّی صحت طبقه­بندی در الگوریتم پیشنهادی و سایر روش­ها در پایگاه داده سرطان پستان


الگوریتم انتخاب ژن

طبقه­بند

صحت طبقه­بندی (٪)

BPSO

BLDA

5/93

PSO

SVM

3/85

GA

SVM

8/95

-

Bayesian

1/74

 

جدول (6): مقایسه نتایج کمّی صحت طبقه­بندی در الگوریتم پیشنهادی و سایر روش­ها در پایگاه داده سرطان پروستات


الگوریتم انتخاب ژن

طبقه­بند

صحت طبقه­بندی (٪)

BPSO

BLDA

9/95

IPSO

KNN

1/92

Hybrid PSO/GA

SVM

4/93

EA

KNN

9/88

 

AML

ALL

 

(الف)

 

 

Relapse

Non relapse

 

 

(ب)

 

 

 

Mesothelioma

ADCA

 

 

(ج)

 

Tumor

Normal

 

 

(د)

شکل (6): مجموعه ژن­های حاوی اطلاعات انتخاب شده با اعمال الگوریتم پیشنهادی در پایگاه­های داده: (الف) سرطان خون؛ (ب) سرطان پستان؛ (ج) سرطان ریه و (د) سرطان پروستات


 

جدول (7): شماره ژن­های مؤثر در بروز سرطان خون به­دست آمده از اعمال الگوریتم پیشنهادی

6362

1249

1745

173

5122

1247

2394

2288

2267

5039

922

6797

2111

6405

1539

2759

2402

4407

 

4549

6378

1882

6919

461

1807

4499

6539

 

1883

248

2121

4229

6376

4096

6677

3847

 

1394

2186

3605

4196

5637

818

2020

4052

 

جدول (8): شماره ژن­های مؤثر در بروز سرطان پستان به­دست آمده از اعمال الگوریتم پیشنهادی

462

16038

23179

12680

18109

3524

19891

8576

659

8071

13490

2141

838

9156

6541

9274

89

11513

1686

11145

14204

22599

20453

7459

16214

4732

512

 

12427

16930

12017

14324

21818

23207

9476

10504

 

6598

6214

10643

13835

9730

13343

2769

18807

جدول (9): شماره ژن­های مؤثر در بروز سرطان ریه به­دست آمده از اعمال الگوریتم پیشنهادی

8172

6571

9474

5248

1673

3361

1612

7000

8858

6106

10570

2205

7069

3902

6405

9228

4331

9064

11957

5853

10664

7249

10859

4336

 

5854

8370

11891

11620

343

11470

4174

 

561

7200

12152

3844

3334

2549

1611

 

جدول (10): شماره ژن­های مؤثر در بروز سرطان پروستات به­دست آمده از اعمال الگوریتم پیشنهادی

11013

6995

8552

306

9341

329

10996

10092

2912

7067

344

4351

11202

6158

5757

8123

11215

549

8716

8965

11818

3703

7896

5155

12448

8378

4365

2839

 

8527

6512

288

1257

12148

7775

 

5- نتیجه‌گیری

 در این مقاله یک الگوریتم جدید و کارآمد بر پایه مدل ترکیبی بهینه­سازی ازدحام ذرات باینری و الگوریتم آنالیز تفکیک­کننده خطی بیز برای انتخاب ژن و طبقه­بندی آن­ها پیشنهاد و عملکرد آن بر روی چهار پایگاه داده ریزآرایه ارزیابی شد. در ابتدا، کلیه نمونه­ها به دو دسته نمونه­های آموزشی و نمونه­های تست با استفاده از روش اعتبارسنجی fold-10 تقسیم گردید. سپس با به­کارگیری آنالیز همبستگی پیرسون، یک مجموعه ژن از نمونه­های آموزشی انتخاب گردید. در مرحله بعد با به­کارگیری الگوریتم BPSO  هر ذره یک مجموعه ژن را انتخاب کرده و سپس میزان تناسب مجموعه ژن انتخاب شده توسط آن ذره با طبقه­بند BLDA محاسبه گردید. بعد از 50 بار تکرار ذره­ای که بهترین میزان تناسب (صحت طبقه­بندی) را داشته است، به­عنوان مجموعه ژن حاوی اطلاعات در نظر گرفته می­شود. نتایج پیاده­سازی نشان داد که الگوریتم پیشنهادی به کاهش بعد داده­های ریزآرایه منجر می­شود. همچنین صحت طبقه­بندی در آن به­علت استفاده از مدل BPSO بهبود می­یابد؛ علت این امر آن است که در مدل BPSO، همبستگی بین ژن­ها در نظر گرفته شده و این امر به از بین رفتن افزونگی و همچنین کاهش تعداد ژن­های فاقد اطلاعات و اضافی منجر می­شود. با این حال، الگوریتم پیشنهادی در برخی موارد عملکرد ضعیفتری نسبت به سایر الگوریتم‌ها دارد. برای مثال در سرطان ریه، صحت طبقه‌بندی در الگوریتم پیشنهادی برابر 5/99 درصد و در الگوریتمPSO-Ensemble Neural Network برابر 100 درصد است. علت این امر، آن است که استفاده از طبقه‌بندهای گروهی نتیجه بهتری از یک طبقه‌بند دارد. هدف ما در کارهای آینده، ترکیب الگوریتم‌های پیشرفته­تر با الگوریتم پیشنهادی به­منظور افزایش نرخ طبقه­بندی خواهد بود.

 



[1]Microarray

[2]Deoxyribonucleic Acid

[3]Spot

[4]Prob

[5]Complementary DNA (cDNA)

[6]Binary Particle Swarm Optimization(BPSO)

[7]Bayesian Linear Discriminant Analysis (BLDA)

[8]Acute Lymphoblastic Leukemia

[9]Acute Myeloid Leukemia

[10]Relapse

[11]Non-Relapse

[12]Malignant Pleural Mesothelioma

[13]Adenocarcinoma

[14]Attribute- Relation File Format

[15]Person Correlation (PC)

[16]Over-fitting

 

 

 

 

 

 

 

 

[1]      Wee, A., Liew, C., Yah, H., and Yang, M., "Pattern recognition techniques for the emerging field of bioinformatics: A review", Pattern Recognition, No. 38, No. 11, pp. 2055 – 2073, 2005.

[2]      Chu, F., and Wang, L., "Application of support vector machines to cancer classification with microarray data", International Journal of Neural Systems, Vol. 15, No. 6, pp. 239-263, 2002.

[3]      Lu, Y., and Han, J., "Cancer Classification Using Gene Expression Data", Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.

[4]      Brazma, A., and Vilo, J., Gene expression data analysis, European Molecular Biology Laboratory, Outstation Hinxton, 2000.

[5]      Molaiezadeh, F., Moradi, M. H, "Informative Gene Selection in Microarray Data using Mutual Informtion and Genetic Algorithm", 13th Conference on Biomedical Engineering, Sharif University of Technology, Tehran, Iran, February 2007.

[6]      Ben-Doe, A., Bruhn, L., Friedman, N., Nachman, I., Schummer, M., and Yakhini, Z., "Tissue classification with gene expression profiles", Journal of Computational Biology, Vol. 7, No. 3-4, pp. 559-583, 2000.

[7]      http:// datam.i2r.a-star.edu.sg/datasets/krbd.

[8]      Chen, Y., and Zhao, Y., "A novel ensemble of classifiers for microarray data classification", Applied Soft Computing, ELSEVIER, No. 8, pp. 1664-1669, 2008.

[9]      Guyon, I. and Elisseeff, A., "An introduction to variable and feature selection", Journal of Machine Learning Research, Vol. 3, No. 3, pp. 1157-1182, 2003.

[10]      Li, L., Weinberg, C. R., Darden, T. A., and Pedersen, L. G., "Gene selection for sample classification based on gene expression data: study of sensitivity to choice of parameters of the GA/KNN method", Bioinformatics, Vol. 17, No. 12, pp. 1131-1142, 2001.

[11]      Jourdan, L., Metheuristics for knowledge discovery: Application to genetic data, Ph.D. thesis, University of Lille, 2003.

[12]      Peng, S., Xu, Q., Ling, X. B., Peng, X., Du, W., and Chen, L., "Molecular classification of cancer types from microarray data using the combination of genetic algorithms and support vector machines", FEBS Letter, Vol. 555, No. 2, pp. 358-362, 2003.

[13]      Reddy, A. R., and Deb, K., Classification of two-class cancer data reliably using evolutionary algorithms, Technical Report, KanGAL, 2003.

[14]      Guyon, I., Weston, J., Barnhill, S., and Vapnik, V., "Gene selection for cancer classification using support vector machines", Machine Learning, Vol. 46, No. 1-3, pp. 389-422, 2002.

[15]      Saeys, Y., Aeyels Degroeve, S., Rouze, D., and Van de peer, Y. P., "Enhancement genetic feature selection through restricted search and Walsh analysis", IEEE Transactions on Systems, Man and Cybernetics, Part C, Vol. 34, pp. 398-406, 2004.

[16]      Goh, L., Song, Q., and Kasabov, N., "A novel feature selection method to improve classification of gene expression data", In Proceedings of the Second Asia-Pacific Conference on Bioinformatics, pages 161-166, Australian Computer Society, Darling Hurst, Australia, 2004.

[17]      Kennedy, J., and Eberhat, R., "Particle Swarm Optimization", In Proceedings of the IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.

[18]      Kennedy, J., and Eberhat, R., "A Discrete Binary Version of the Particle Swarm Algorithm", In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Vol.5, pp. 4104-4109, 1997.

[19]      Hoffmann, U., Vesin, J. M., Ebrahimi, T., and Diserens, K., "An efficient P300-based brain computer interface for disables subjects", Journal of Neuroscience Methods, Vol. 2, No. 2, pp. 1-5, 2007.

[20]      Hoffmann, U., Bayesian machine learning applied in a brain computer for disabled users, Ph.D. thesis, 2007.

[21]      Hoffmann, U., "Bayesian feature selection applied in a P300 brain-computer interface", Vol. 2, No. 3, pp. 1-5, 2007.

[22]      Chuang, L., Chang, H., Tu, C., and Yang, C., "Improved binary PSO for feature selection using gene expression data", Computational Biology and Chemistry, ELSEVIER, Vol. 1, No. 32, pp. 29-38, 2008.

[23]      Chen, Y., and Zhao, Y., "A novel ensemble of classifiers for microarray data classification", Applied Soft Computing, Elsevier, Vol. 8, No. 4, pp. 1664-1669, 2008.

[24]      Wang, Z. Y., Palade, V., and Xu, Y., "Nero-fuzzy ensemble approach for microarray cancer gene expression data analysis", In Proceeding of the International Symposium on Evolving Fuzzy Systems, pp. 241-246, 2006.

[25]      Jirapech,-Umpai, T., and Aitken, S, "Feature selection and classification for microarray data analysis: Evolutionary methods for identifying predictive genes", Bioinformatics, Vol. 6, No. 3, pp. 168-174, 2005.

[26]      Sharma, A., and Paliwal, K., "A gene selection algorithm using Bayesian classification approach", American Journal of Applied Sciences, Vol. 9, No. 1, pp. 127-131, 2012.

[27]      Alba, E., Garcia-Nieto, J., Jourdan, L., and Ghazali Talbi, El., "Gene selection in cancer classification using PSO/SVM and GA/SVM hybrid algorithms", IEEE Congress on Evolutionary Computation (CEC 2007), 2007.

[28]      Chuang, L. Y., Chang, H. W., Tu, C. J., and Yang, C. H., "Improved binary PSO for feature selection using gene expression data", Computational Biology and Chemistry, Elsevier, Vol. 32, No. 1, pp. 29-38, 2008.

[29]      Li, S., Wu, X., and Tan, M., "Gene selection using hybrid particle swarm optimization and genetic algorithm", Soft Computing, Springer, Vol. 12, pp. 1039-1048, 2008.

[30]          Juliusdottir, D., Corne, E., Keedwell, E., and Narayanan, A., "Two-phase EA/KNN for feature selection and classification in cancer microarray datasets", In CIBCB, pp. 1-8, 2005.

[31]        T. Li, C.L. Zhang, M. Ogihara, "A comparative study of feature selection and multiclass classification methods for tissue classification based on gene expression", Bioinformatics 20, No. 15, pp. 2429–2437, 2004.