Dead-end elimination

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

דרישות

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

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

יישומים

ניבוי מבנה חלבונים

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

נסמן $N$ כאורך החלבון ו $r_{k}$ כרוטמר של השייר $\mathrm {k^{th}}$. תחת ההנחה שאטומים בחלבון פועלים זה על זה כפוטנציאל בין שני גופים בלבד ניתן לייצג את האנרגיה באופן הבא:

$E_{TOT}=\sum _{k}E_{k}(r_{k})+\sum _{k\neq l}E_{kl}(r_{k},r_{l})\,$

כאשר $E_{k}(r_{k})$ מייצג את "האנרגיה העצמית" של רוטמר מסוים $r_{k}$, ו-$E_{kl}(r_{k},r_{l})$ מייצג את "אנרגיית הזוג" של הרוטמרים $r_{k},r_{j}$.

כמו כן $E_{kk}(r_{k}^{A},r_{k}^{A})$ (אנרגיית הזוג של הרוטמר עם עצמו) נלקחת כאפס, ואינה משפיעה על הסכימה. סימון זה מפשט את התיאור לעיל.

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

קריטריון אלימינציה לרוטמרים יחידים

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

$E_{k}(r_{k}^{A})+\sum _{l=1}^{N}\min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})>E_{k}(r_{k}^{B})+\sum _{l=1}^{N}\max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})$

כאשר $\min _{X}E_{kl}(r_{k}^{A},r_{l}^{X})$ האו האנרגיה המינימלית האפשרית (העדיפה) בין הרוטמר $r_{k}^{A}$ של שייר $k$ וכל רוטמר X של שייר $l$. בצורה דומה, $\max _{X}E_{kl}(r_{k}^{B},r_{l}^{X})$ הוא האנרגיה המקסימלית האפשרית (הגרועה ביותר) בין הרוטמר $r_{k}^{B}$ של שייר $k$ וכל רוטמר X של שייר $l$.

קריטריון אלימינציה זוגי

קריטריון אלימינציה על זוגות קשה יותר לתיאור ומימוש, אולם הוא מוסיף עוצמה רבה לאלימינציה. נסמן $U_{kl}^{AB}$ כאנרגיה הפנימית של זוג רוטמרים $A$ ו-$B$ במיקומים $k$ and $l$

$U_{kl}^{AB}\ {\stackrel {\mathrm {def} }{=}}\ E_{k}(r_{k}^{A})+E_{l}(r_{l}^{B})+E_{kl}(r_{k}^{A},r_{l}^{B})$

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

$U_{kl}^{AB}+\sum _{i=1}^{N}\min _{X}\left(E_{ki}(r_{k}^{A},r_{i}^{X})+E_{lj}(r_{l}^{B},r_{j}^{X})\right)>U_{kl}^{CD}+\sum _{i=1}^{N}\max _{X}\left(E_{ki}(r_{k}^{C},r_{i}^{X})+E_{lj}(r_{l}^{D},r_{j}^{X})\right)$

כאשר $A\neq C$, $B\neq D$ ו-$k\neq l$.

תכנון חלבונים

בניבוי מבנה של חלבון קיימת ההנחה כי רצף החלבון קבוע, ולכן הרוטמרים $r_{k}$ הם כולם רוטמרים של שייר של חומצת אמינו מסוימת. ניתן גם לאפשר למספר שיירים של חומצות אמינו "להתחרות" על המיקום $k$ על ידי הכללה סוגי השיירים בקבוצת הרוטמרים לפי המיקום. בצורה זו ניתן לתכנן רצף חדש לשלד חלבון נתון. בצורה זו תוכנן מחדש חלבון Zinc finger קצר.

לקריאה נוספת

• 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.{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)