فهرست مطالب
عنوان مطالب فهرست
چکیده. 1
فصل اول: کلیات تحقیق.. 1
1-1- پیشگفتار. 3
1-2- مفاهیم زیستی.. 6
1-2-1. سلول و اجزای آن. 6
1-2-2. مولکولهای زیستی و بیان ژن. 6
1-3- مفاهیم کامپیوتری.. 11
1-3-1. نظریه گراف و شبکه. 11
1-3-2. موتیف… 15
1-4- اشیای خودمتشابه و هندسه فرکتالی.. 22
فصل دوم: مروری بر پیشینه تحقیق.. 2
2-1- الگوریتم Pajek. 27
2-2- الگوریتم mfinder 28
2-3- الگوریتم (FPF)MAVisto. 31
2-4- الگوریتم NeMoFinder 33
2-5- الگوریتم (ESU)FANMOD.. 39
2-6- الگوریتم Grochow-Kellis. 40
2-7- الگوریتم MODA.. 44
2-8- الگوریتم kavosh. 46
2-8-1. الگوریتم CytoKavosh. 48
2-9- الگوریتم G-Tries. 50
2-10- الگوریتم QuateXelero. 54
2-11- بحث و بررسی الگوریتمهای کشف موتیف موجود. 62
فصل سوم: روش پیشنهـادی… 68
3-1- پیادهسازی الگوریتم. 69
3-1-1. شبکه مولتیفرکتال. 69
3-1-2. رویکرد 1 (multifractal network generator + Quatexelero): 73
3-1-3. رویکرد 2 (multifractal network generator + maximal likelihood estimation): 75
فصل چهارم: نتـایج آزمایش…. 61
4-1- پایگاه دادههای مورد استفاده ، جهت ارزیابی الگوریتم پیشنهادی.. 80
4-2- نتایج الگوریتم پیشنهادی بر روی شبکههای پیچیده 81
فصل پنجم: نتیجه گیری و پیشنهادها 93
5-1- نتیجهگیری.. 94
5-2- پیشنهادهای آتی.. 95
منابع فارسی… 97
منابع انگلیسی… 98
ضمائم. 100
Abstract 101
فهرست جداول
جدول 1‑1- تعداد گرافهای ساده جهتدار و بدونجهت غیرایزومورفیسم. 17
جدول 1‑3- محاسبه بعد اقلیدسی خط ، مربع و مکعب… 22
جدول 2‑1- مقایسه روش نمونهبرداری و شمارش… 30
جدول 2‑2- تعداد زیرگرافهای شمارش شده، بدون حذف تقارن در شبکه PPI و مخمر. 43
جدول 2‑3-شبکههای مورد ارزیابی توسط الگوریتمهای g-tries و FANMOD… 53
جدول 2‑4-مقایسه الگوریتم g-trie با الگوریتمهای قبلی(زمان بر حسب ثانیه) 54
جدول 2‑5-مقایسه الگوریتم Kavosh و QuateXelero. 58
جدول 2‑6-مقایسه الگوریتم QuateXelero و G-trie برای موتیفهای کوچک… 61
جدول 2‑7-مقایسه الگوریتم QuateXelero و G-trie برای موتیفهای بزرگ… 61
جدول 2‑8-زمان اجرای الگوریتم mfinder ، FANMOD ، Mavisto و Kavosh برای زیرگراف با اندازه 3 تا 10. 64
جدول 2‑9-زمان اجرای الگوریتم Grochow-Kellis ، FANMOD و G-Trie برای زیرگراف با اندازه 3 تا 9. 64
جدول 2‑10- هزینه محاسباتی الگوریتم Kavosh و FANMOD بر روی شبکه Homo sapiens (زمان بر حسب ثانیه) 65
جدول 2‑11 – هزینه محاسباتی الگوریتم Kavosh و FANMOD بر روی شبکه Drosophila melanogaster PPI network (زمان بر حسب ثانیه) 65
جدول 2‑12-محدودیتهای رخداده در آزمایشات الگوریتم QuateXelero و G-Trie+ESU… 65
جدول 2‑13-زمان اجرای الگوریتم kavosh و QuateXelero در شبکههای جهتدار برای موتیفهای با اندازه 11k≤≥3. 67
جدول 3‑1-تولید شبکه مولتیفرکتال تا مرحلهی L=3. 70
جدول 3‑2 – ماتریس احتمالات بدست آمده شبکهی Dolphins – مرحلهی L=1, 2, 3. 72
جدول 3‑3-توزیع گرههای شبکهی Dolphins بر اساس مجموع احتمالات سطری و ستونی.. 73
جدول 3‑4-توزیع گرههای شبکه Dolphins در ناحیههای مختلف متناظر در ماتریس احتمالات… 74
جدول 3‑5 – تعداد زیرگرافهای متصل و بدونجهت با k راس… 77
جدول 4‑1-شبکههای پیچیده مورد ارزیابی در الگوریتم پیشنهادی.. 80
جدول 4‑2-نتایج بدست آمده بر اساس الگوریتم پیشنهادی برای موتیفهای با اندازه 3 k 15. 85
جدول 4‑3 – نتایج بدست آمده بر اساس الگوریتم پیشنهادی برای موتیفهای با اندازه 16 k 20. 85
جدول 4‑4 -زمان اجرای الگوریتم پیشنهادی و QuateXelero در شبکههای بدونجهت برای موتیفهای با اندازه 11k≤≥3 86
جدول 4‑5 -زمان اجرای الگوریتم پیشنهادی و G-tries در شبکههای بدونجهت برای موتیفهای با اندازه 11k≤≥3. 87
فهرست نمودارها
نمودار 2‑1 – تفاوت زمان اجرا برای 1000 نمونه زیرگراف، با اندازهی متفاوت… 31
نمودار 2‑2 – مقایسه زمان محاسباتی جستجوی موتیفهای شبکه در Uetz PPI network. 37
نمودار 2‑3 -مقایسه زمان محاسباتی جیتجوی کشف موتیفها در شبکه Uetz PPI network با احتساب حد آستانه. 38
نمودار 2‑4 -مقایسه اندازه و تعداد موتیفهای شبکهی کشف شده توسط MIPS PPI network. 38
نمودار 2‑5 – زمان اجرای الگوریتم نسبت به روشهای قبلی.. 43
نمودار 2‑6 – میزان برتری الگوریتم QuateXelero نسبت به G-trie (معیار Equality Point) 59
نمودار 3‑1 – الگوهای فرکتالی موجود در طبیعت… 23
نمودار 3‑2 -نمودار محدودهی توزیع اتصالات شبکه، بر اساس ماتریس احتمالات پس از محاسبه mle-شبکهی Dolphins. 77
نمودار 4‑1 – میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه Dolphins. 81
نمودار 4‑2 – میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه Circuit 82
نمودار 4‑3 – میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه E.coli 82
نمودار 4‑4 – میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه Yeast 83
نمودار 4‑5 – میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه NetScience. 83
نمودار 4‑6 -میزان اختلاف نتایج تخمینی الگوریتم پیشنهادی و الگوریتم QuateXelero در شبکه USPowerGrid. 84
نمودار 4‑7 – اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکه Dolphins. 89
نمودار 4‑8-اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکهی Circuit 89
نمودار 4‑9-اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکهی E.coli 90
نمودار 4‑10-اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکهی Yeast 90
نمودار 4‑11-اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکهی NetScience. 91
نمودار 4‑12-اختلاف رشد بین زمان اجراهای QuateXelero و الگوریتم پیشنهادی-شبکهی USPowerGrid. 91
نمودار 4‑13 – افزایش زمان اجرای الگوریتم پیشنهادی بر اساس افزایش تعداد رئوس و یالهای شبکهی پیچیده 92
نمودار 5‑1 – میزان تاثیر ε در شمارش موتیفِ الگوریتم پیشنهادی.. 94
فهرست تصاویر
تصویر 1‑1- زیرشاخههای گوناگون بیوانفورماتیک… 4
تصویر 1‑2- ساختار سلولِ موجود زنده 6
تصویر 1‑3 – قند دئوکسی ریبوز(سمت راست)، قند ریبوز(سمت چپ) 7
تصویر 1‑4 – ساختار رشته پلی نوکلئوتیدی.. 8
تصویر 1‑5 – دئوکسی ریبونوکلئیک اسید(سمت راست) و ریبونوکلئیک اسید(سمت چپ) 8
تصویر 1‑6 – نمای سه بعدی مولکول پروتئین.. 9
تصویر 1‑7 – مراحل چهارگانهی بیان ژن. 10
تصویر 1‑8 – جریان اطلاعات از ژن تا متابولیسمِ سلول. 10
تصویر 1‑9- زیرگرافهای مشتق شدهی گراف اصلی.. 11
تصویر 1‑10- گرافهای ایزومورفیسم(یکریخت) 11
تصویر 1‑11- گراف بدونجهت، گراف جهتدار، گراف ترکیبی(از سمت چپ) 12
تصویر 1‑12- نمونهای از گراف چندگانه. 12
تصویر 1‑13- نمونه ای از شبکه بیولوژیک… 13
تصویر 1‑14- نمایش موتیف در شبکه فرضی.. 15
تصویر 1‑15 – موتیف حلقه feed-forward در شبکه تنظیم ژن مخمر. 15
تصویر 1‑16- مفاهیم میزان تکرار موتیف بر روی گراف پایه a. 16
تصویر 1‑17- موتیف Self-Edge. 20
تصویر 1‑18- موتیف Feed-Forward Loops. 21
تصویر 1‑19- نمونهای از موتیفهای شبکه. 21
تصویر 1‑20 – تصویر خودمتشابه کلم بروکلی.. 22
تصویر 1‑21- ایجاد شی فرکتالی(خودمتشابه) 24
تصویر 2‑1- گسترش درخت الگو توسط الگوریتم FPF.. 32
تصویر 2‑2 – گراف G… 33
تصویر 2‑3- درختهای با اندازه 2 تا 5. 34
تصویر 2‑4 – رخدادن درخت در گراف G… 34
تصویر 2‑5 – رخدادن درخت در گراف G… 34
تصویر 2‑6 – مجموعه گرافهای .. 35
تصویر 2‑7 – تولید زیرگراف با 3 یال از درخت با اندازه 4. 35
تصویر 2‑8- مراحل اتصال گراف برای زیرگرافهای با سه یال. 35
تصویر 2‑9 – تولید زیرگراف با 4 یال از تکرار زیرگرافهای G با 4 یال. 36
تصویر 2‑10- مراحل اتصال گراف برای زیرگرافهای با 4 یال. 36
تصویر 2‑11- نگاشت ممکن یک زیرگراف به حالتهای مختلف… 41
تصویر 2‑12- ماتریس مجاورتِ یک نمونه گراف… 47
تصویر 2‑13-عملیات جابجایی یالها برای تولید شبکه تصادفی.. 47
تصویر 2‑14 – نمونه ترای نمایشدهنده کلمات… 50
تصویر 2‑15- مراحل درج سه گراف در g-trie خالی.. 51
تصویر 2‑16- مثالی از روال شمارش در الگوریتم g-trie. 52
تصویر 2‑17- ساختار درخت چهارتایی در QuateXelero. 54
تصویر 2‑18-جستجوی یک نمونه درخت چهارتایی برای رشته ورودی “321”. 55
تصویر 2‑19-مراحل طبقه بندی یک زیرگراف، در حال افزودن یک برگ به درخت چهارتایی.. 56
تصویر 2‑20-مراحل طبقهبندی یک زیرگراف، برای رسیدن به برگ موجود در مرحله قبلی در درخت چهارتایی.. 56
تصویر 2‑21-مراحل شمارش زیرگراف بر اساس رشته ورودی در الگوریتم QuateXelero. 57
تصویر 3‑1- نحوه محاسبه سلولهای شبکه مولتیفرکتال نسبت به ماتریس پایه. 71
تصویر 3‑2 -نمونهای از توپولوژی شبکهی Dolphins بر اساس ماتریس احتمالات… 73
تصویر 3‑5-تابع ماکزیمم درستنمایی(Maximal Likelihood Estimation) 76
تصویر 5‑1- رئوس ناامیدبخشِ شبکهی پیچیدهی باکتری E.Coli 95
فهرست معادلات
معادله 1‑1 – حداکثر تعداد یالها در شبکه بدون جهت… 14
معادله 1‑2 – ضریب خوشهبندی.. 15
معادله 1‑3 – میزان اختلاف تکرار موتیف در شبکه هدف… 18
معادله 1‑4 – احتمال کشف موتیف در شبکه تصادفی.. 18
معادله 1‑5- فاصله نسبی میزان تکرار graphlet 19
معادله 1‑6 – مجموع لگاریتم تکرار نسبی graphlet 19
معادله 2‑1 – تعداد کل زیرگرافهای متصل با n گره در شبکه. 28
معادله 2‑2- احتمال نمونهبرداری زیرگراف در mfinder. 29
معادله 2‑3 – محاسبه میزان تکرار زیرگرافها 49
معادله 2‑4 – محاسبه Zscore. 49
معادله 2‑5 – نرخ فشرده سازی جهت صرفهجویی در حافظه. 51
معادله 2‑6- محاسبه Zscore. 58
معادله 2‑7 – میزان اختلاف زمان اجرای دو الگوریتم کشف موتیف… 59
معادله 3‑1- بعد اقلیدسی شی فرکتالی.. 22
معادله 3‑2- محاسبه احتمال هر واحد بر اساس اتصالات ناحیه متناظر در ماتریس مجاورت شبکه. 70
معادله 3‑3-موقعیت حداکثر تابع MLE.. 75
معادله 3‑4 -محاسبه تعداد تخمینی موتیف در شبکههای پیچیده توسط الگوریتم پیشنهادی.. 78
فهرست الگوریتمها
الگوریتم 2‑1- الگوریتم نمونهبرداری زیرگرافها در mfinder. 29
الگوریتم 2‑2- نحوه محاسبه نمونه برداری زیرگرافهای مختلف در mfinder. 29
الگوریتم 2‑3- الگوریتم یافتن گرافهای تکراری.. 36
الگوریتم 2‑4- یافتن همه نمونههای گراف پرس و جوی H در شبکه G.. 40
الگوریتم 2‑5- الگوریتم جستجوی همه نگاشتهای ایزومورفیسم 41
الگوریتم 2‑6- الگوریتم یافتن شرایط حذف تقارن. 42
الگوریتم 2‑7- الگوریتم میزان تکرار زیرگرافها 45
الگوریتم 2‑8- ماژول نگاشتِ الگوریتم MODA.. 45
الگوریتم 2‑9- ماژول شمارش الگوریتم MODA.. 45
الگوریتم 2‑10- الگوریتم درج گراف در یک درخت ترای.. 51
الگوریتم 2‑11 – الگوریتم شمارش زیرگرافهای T در گراف G.. 52
الگوریتم 2‑12-الگوریتم بررسی شرایط حذف تقارن برای گراف G.. 53
الگوریتم 2‑13- الگوریتم درج گراف G در g-trie و شمارش زیرگرافهای T در گراف G با شرط حذف تقارن. 53
الگوریتم 2‑14-الگوریتم QuateXelero. 55
علایم اختصاری و اصطلاحات
DNA |
Deoxyribonucleic acid |
RNA |
Ribonucleic acid |
A |
Adenine |
G |
Guanine |
C |
Cytosine |
T |
Thymine |
rRNA |
Ribosomale RNA |
mRNA |
messenger RNA |
tRNA |
Transfer RNA |
NAR |
Negative auto-regulation |
TF |
transcription factor |
PAR |
Positive auto-regulation |
FFL |
Feed-forward loops |
P-Value |
probability value |
Z-Score |
Standard(Z distribution) score |
FPF |
flexible pattern finder |
NeMoFinder |
Network motif finder |
FANMOD |
fast network motif detection |
MODA |
Motif discovery algorithm |
mfng |
Multifractal network generator |
mle |
Maximal Likelihood Estimation |
Mavisto |
Motif Analysis and VISualization TOol |
