Dead-end elimination

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

אלגוריתם dead-end elimination ‏(DEE) היא שיטת מיטוב למציאת ערכים מינימליים בפונקציה עם קבוצה בדידה של משתנים בלתי תלויים. השיטה מתבססת על זיהוי "dead ends", או קומבינציות "גרועות" של משתנים שלא צפוי שיניבו מינימום גלובלי ולהימנע מחיפוש קומבינציות כאלו להבא. שיטה זו היא אפוא תמונת ראי לתכנון דינמי, שבה קומבינציות "טובות" מזוהות ונחקרות. אף על פי ששיטה זו היא כללית, השיטה פותחה ויושמה בעיקר לתחום של ניבוי מבני חלבונים ולתכנון חלבונים.

דרישות[עריכת קוד מקור | עריכה]

לשימוש ב-Dead-end elimination נדרש להגדיר מספר מאפיינים:

  1. קבוצה סגורה ומוגדרת היטב של משתנים בדידים בלתי תלויים
  2. ערך מספרי שחושב קודם (מוגדר כ"אנרגיה") הקשור לכל איבר בקבוצת המשתנים (וייתכן לזוגות, שלשות וכו')
  3. קריטריון לקביעה האם איבר הוא "dead end", כלומר מתי האיבר לא יכול להיות בקבוצת הפתרון
  4. פונקציית מטרה (objective function; או "פונקציית אנרגיה") שבה מחפשים מינימום

יישומים[עריכת קוד מקור | עריכה]

ניבוי מבנה חלבונים[עריכת קוד מקור | עריכה]

שיטת Dead-end elimination נמצאת בשימוש נרחב לניבוי מבנה של שיירי חומצות אמינו בשלד נתון של מבנה חלבון באמצעות מציאת מינימום לפונקציית אנרגיה E. מרחב החיפוש של זווית הדו-מישור של שיירי חומצות האמינו מוגבל לקבוצה בדידה של רוטמרים לכל מיקום של חומצת אמינו.

נסמן כאורך החלבון ו כרוטמר של השייר . תחת ההנחה שאטומים בחלבון פועלים זה על זה כפוטנציאל בין שני גופים בלבד ניתן לייצג את האנרגיה באופן הבא:

כאשר מייצג את "האנרגיה העצמית" של רוטמר מסוים , ו- מייצג את "אנרגיית הזוג" של הרוטמרים .

כמו כן (אנרגיית הזוג של הרוטמר עם עצמו) נלקחת כאפס, ואינה משפיעה על הסכימה. סימון זה מפשט את התיאור לעיל.

לרוב מופעלים שני הקריטריונים הבאים לאלימינציה (היחיד והזוגי) בצורה איטרטיבית עד להתכנסות, נקודה שבה לא ניתן עוד לעשות אלימנציה לרוטמרים או לזוגות. שיטה זו עשויה להקטין את מרחב החיפוש בסדרי גודל רבים, ולאחר מכן די במעבר פשוט על האפשרויות הנותרות למציאת המינימום.

קריטריון אלימינציה לרוטמרים יחידים[עריכת קוד מקור | עריכה]

אם רוטמר מסוים של שייר לא יכול לתת אנרגיה טובה יותר משל רוטמר אחר של אותו השייר, אז ניתן לעשות אלימינציה לרוטמר A מחישובים בהמשך, וכך קטן מרחב החיפוש. בצורה מתמטית תנאי זה מבוטא באמצעות אי השוויון:

כאשר האו האנרגיה המינימלית האפשרית (העדיפה) בין הרוטמר של שייר וכל רוטמר X של שייר . בצורה דומה, הוא האנרגיה המקסימלית האפשרית (הגרועה ביותר) בין הרוטמר של שייר וכל רוטמר X של שייר .

קריטריון אלימינציה זוגי[עריכת קוד מקור | עריכה]

קריטריון אלימינציה על זוגות קשה יותר לתיאור ומימוש, אולם הוא מוסיף עוצמה רבה לאלימינציה. נסמן כאנרגיה הפנימית של זוג רוטמרים ו- במיקומים and

עבור זוג נתון של רוטמרים ו- במיקומים ו-, בהתאמה, לא יכולים להיות יחדיו התוצאה הסופית (אם כי ייתכן שאחד מהם יהיו), אם קיים זוג נוסף ו- אשר נותן תמיד אנרגיה נמוכה יותר, ובניסוח מתמטי:

כאשר , ו-.

תכנון חלבונים[עריכת קוד מקור | עריכה]

בניבוי מבנה של חלבון קיימת ההנחה כי רצף החלבון קבוע, ולכן הרוטמרים הם כולם רוטמרים של שייר של חומצת אמינו מסוימת. ניתן גם לאפשר למספר שיירים של חומצות אמינו "להתחרות" על המיקום על ידי הכללה סוגי השיירים בקבוצת הרוטמרים לפי המיקום. בצורה זו ניתן לתכנן רצף חדש לשלד חלבון נתון. בצורה זו תוכנן מחדש חלבון Zinc finger קצר[1].

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Desmet J, de Maeyer M, Hazes B, Lasters I (1992). "The dead-end elimination theorem and its use in protein side-chain positioning". Nature 356: 539–542. doi:10.1038/356539a0. 

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Dahiyat BI, Mayo SL. (1997). De novo protein design: fully automated sequence selection. Science 278(5335):82-7.