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}$ כרוטמר של השייר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{k^{th}}} . תחת ההנחה שאטומים בחלבון פועלים זה על זה כפוטנציאל בין שני גופים בלבד ניתן לייצג את האנרגיה באופן הבא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{TOT} = \sum_{k} E_{k}(r_{k}) + \sum_{k \neq l} E_{kl}(r_{k}, r_{l})\, }

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{k}(r_{k})} מייצג את "האנרגיה העצמית" של רוטמר מסוים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}} , ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_{kl}(r_{k}, r_{l})} מייצג את "אנרגיית הזוג" של הרוטמרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}, r_{j}} .

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

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

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

אם רוטמר מסוים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}^{A}} של שייר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} לא יכול לתת אנרגיה טובה יותר משל רוטמר אחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}^{B}} של אותו השייר, אז ניתן לעשות אלימינציה לרוטמר A מחישובים בהמשך, וכך קטן מרחב החיפוש. בצורה מתמטית תנאי זה מבוטא באמצעות אי השוויון:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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}) }

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min_{X} E_{kl}(r_{k}^{A}, r_{l}^{X})} האו האנרגיה המינימלית האפשרית (העדיפה) בין הרוטמר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}^{A}} של שייר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} וכל רוטמר X של שייר $l$. בצורה דומה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max_{X} E_{kl}(r_{k}^{B}, r_{l}^{X})} הוא האנרגיה המקסימלית האפשרית (הגרועה ביותר) בין הרוטמר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{k}^{B}} של שייר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} וכל רוטמר X של שייר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} .

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

קריטריון אלימינציה על זוגות קשה יותר לתיאור ומימוש, אולם הוא מוסיף עוצמה רבה לאלימינציה. נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{kl}^{AB}} כאנרגיה הפנימית של זוג רוטמרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} במיקומים $k$ and הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{kl}^{AB} \ \stackrel{\mathrm{def}}{=}\ E_{k}(r_{k}^{A}) + E_{l}(r_{l}^{B}) + E_{kl}(r_{k}^{A}, r_{l}^{B}) }

עבור זוג נתון של רוטמרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} במיקומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} , בהתאמה, לא יכולים להיות יחדיו התוצאה הסופית (אם כי ייתכן שאחד מהם יהיו), אם קיים זוג נוסף $C$ ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} אשר נותן תמיד אנרגיה נמוכה יותר, ובניסוח מתמטי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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) }

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \neq C} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B \neq D} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \neq l} .

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

בניבוי מבנה של חלבון קיימת ההנחה כי רצף החלבון קבוע, ולכן הרוטמרים $r_{k}$ הם כולם רוטמרים של שייר של חומצת אמינו מסוימת. ניתן גם לאפשר למספר שיירים של חומצות אמינו "להתחרות" על המיקום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)