הצגת המקור של הדף "עימוד רצפים"

ב[[ביואינפורמטיקה]], '''עימוד רצפים''' היא שיטה לסידור המידע על אודות רצפי [[DNA]] ,[[RNA]] או [[חלבונים]], בצורה כזו שיהיה ניתן לזהות אזורים דומים, אשר ייתכן כי הם תוצאה של קשרים פונקציונלים, מבניים או אבולוציוניים.

עימוד רצפי של [[נוקלאוטידים]] או שיירי [[חומצת אמינו|חומצות אמינו]] מיוצגים לרוב על ידי שורות ב[[מטריצה]]. רווחים מוכנסים בין הרצפים כך שרצפים דומים מעומדים בעמודות.
ההשוואה בין הרצפים המעומדים מקבלת ציון [[הומולוגיה (ביולוגיה)|הומולוגיה]] אשר עשוי להעיד על פעילות ביולוגית דומה של הרצפים. על האבולוציה של הרצפים אפשר ללמוד דרך ניתוח [[הומולוגיה של רצף]]. לרישום הרצפים פותח [[פורמט FASTA]].

[[קובץ:Zinc-finger-seq-alignment2.png|מסגרת|מרכז|עימוד רצפים שנוצר על ידי [[ClustalW]] של שני חלבוני zinc finger אשר פוענחו.
<br>
מפתח: אותיות בודדות: [[חומצת אמינו|חומצות אמינו]]. אדום: קטנות, הידרופוביות, ארומטיות, לא Y. כחול: חומציות. סגול: בסיסיות. ירוק: [[הידרוקסיל]], אמין, אמיד, בסיסיות. אפור: אחרות.
<br>
"*" : זהות .":": שינויים שמורים (אותה קבוצת צבעים). ".": שינויים שמורים-למחצה (מבנה דומה).
]]

[[קובץ:RPLP0 90 ClustalW aln.gif|מרכז|ממוזער|600px|דוגמה לתוצאות של [[Multiple sequence alignment]]]]

אלגוריתמים נפוצים לעימוד רצפים המבוססים על [[תכנון דינמי]] הם אלגוריתם נידלמן וונש (Needleman-Wunsch), המיועד לעימוד רצפים גלובלי, ואלגוריתם סמית-ווטרמן (Smith-Waterman) המיועד לעימוד רצפים לוקלי (מציאת אזורים דומים במחרוזות של דנ"א או חומצות אמינו).

==עימוד רצפים באמצעות תכנון דינמי==
===עימוד רצפים גלובלי===
כאשר נתונה [[מטריצת החלפות]] (כדוגמת [[BLOSUM|BLOSUM62]] או [[PAM|PAM250]]), המגדירה את ציון לכל החלפה של אותיות וכאשר ניתן ציון חוסר באות, הציון לעימוד של שני רצפים מוגדר כסכום הציונים לכל העמדות. בעיית עימוד רצפים גלובלי היא בעיה שבה מתאימים בין כל אות ברצף אחד לאות ברצף השני כאשר שני הרצפים דומים, במטרה למצוא את העימוד הטוב ביותר, במובן שציון העימוד יהיה מקסימלי.

לדוגמה כאשר הציון של אות חסרה הוא -5 ונעשה שימוש במטריצת החלפות הבאה:
{| style="font-family: monospace;font-size:150%;direction:ltr;" class="wikitable" cellpadding="2"
! scope="col" |
! scope="col" | A
! scope="col" | G
! scope="col" | C
! scope="col" | T
|- style="text-align: right;"
! scope="row" | A
| 10 || -1 || -3 || -4
|- style="text-align: right;"
! scope="row" | G
| -1 || 7 || -5 || -3
|- style="text-align: right;"
! scope="row" | C
| -3 || -5 || 9 || 0
|- style="text-align: right;"
! scope="row" | T
| -4 || -3 || 0 || 8
|}
ניתן לחשב ציון עבור עימוד של שני רצפים:
{| border="1" class="wikitable"
!רצף א'
| A || G || A || C || T || A || G || T || T || A || C
|-
! רצף ב'
| C || G || A || - || - || - || G || A || C || G || T
|- style="direction:ltr;"
! ציון
| -3 || 7 || 10 || -5 || -5 || -5 || 7 || -4 || 0 || -1 || 0
|}
הציון הכולל המתקבל מסכימת הציונים על כל העמדות בדוגמה לעיל 1.

[[קובץ:Needleman-Wunsch pairwise sequence alignment.png|ממוזער|250px|אלגוריתם נידלמן-וונש]]
'''אלגוריתם נידלמן וונש''' (Needleman-Wunsch){{כ}}{{הערה|שם=Needleman|1={{cite journal | journal=Journal of Molecular Biology | volume=48 | issue=3 | pages=443–53 | year=1970  | author=Needleman, Saul B.; and Wunsch, Christian D. | title=A general method applicable to the search for similarities in the amino acid sequence of two proteins | url=http://linkinghub.elsevier.com/retrieve/pii/0022-2836(70)90057-4 | pmid=5420325 | doi = 10.1016/0022-2836(70)90057-4 }}}} מיועד לפתור בעיה זו ביעילות (סיבוכיות זמן ומקום של <math> \ O(n^2) </math> - עבור רצפים באורך n) תוך שימוש ב[[תכנון דינמי]], באמצעות מילוי מטריצת <math>F_{ij}</math>, המגדירה את ציון העימוד המיטבי עבור תת-המחרוזת מ-A המתחילה מהאות האפס (מחרוזת ריקה) ונגמרת באות ה-<math>i=0,\dotsc,n</math> ותת המחרוזת ב-B המתחילה באפס ונגמרת באות ה-<math>j=0,\dotsc,m</math>. הטבלה מוגדרת על פי הבסיס (שורה אפס ועמודה אפס):
:<math>F_{0j} = d*j</math>
:<math>F_{i0} = d*i</math>
והרקורסיה (יתר המטריצה) מאותחלת על פי ערך העימוד המיטבי:
:<math>F_{ij} = \max \begin{Bmatrix}
F_{i-1,j-1}+ \ w(A_i,B_j) & \text{Match/Mismatch} \\
F_{i-1,j} + \ d & \text{Deletion} \\
F_{i,j-1} + \ d & \text{Insertion}
\end{Bmatrix}
,\; 1\le i\le n, 1\le j\le m
</math>

כאשר: <math>w(a,b),\; a, b\in\Sigma</math> מגדיר את הציון להחלפה ו-d מציין ציון לרווח.

ציון העימוד המיטבי עבור הרצף A והרצף B מוגדר על פי <math>F_{nm}</math>, כאשר את העימוד המתאים לציון זה (העימוד המיטבי) ניתן למצוא באמצעות מילוי טבלה נוספת המגדירה מצביעים בהתאם לבחירה ובסיום לפעול ב[[גישוש נסוג|עקיבה לאחור]] (Backtracking) החל מהתא המתאים -<math>F_{nm}</math>.

===עימוד רצפים מקומי===
בבעיית עימוד רצפים מקומי המטרה היא למצוא אזור (תת רצף) המתאים ביותר בין שני רצפים (אך לא נדרש עימוד לרצף המלא). '''אלגוריתם סמית-וטרמן''' (Smith-Waterman) {{כ}}{{הערה|שם=Smith1981|1={{cite journal |author=Smith, Temple F.; and Waterman, Michael S. |title=Identification of Common Molecular Subsequences |journal=[[Journal of Molecular Biology]] |volume=147 |pages=195–197 |year=1981 |url=http://gel.ym.edu.tw/~chc/AB_papers/03.pdf |doi=10.1016/0022-2836(81)90087-5 |pmid=7265238 |access-date=2014-01-31 |archive-url=https://web.archive.org/web/20120717060814/http://gel.ym.edu.tw/~chc/AB_papers/03.pdf |archive-date=2012-07-17 |url-status=dead }}}} פותר בעיה זו בסיבוכיות זמן ומקום של <math> \ O(n^2) </math> (עבור רצפים באורך n). באלגוריתם זה ממלאים טבלה <math>F_{ij}</math> המגדירה את העימוד המיטבי ל[[מוספית|סיפא]] של הרצף A מ-0 (מחרוזת ריקה) ועד האות i, ולסיפא של הרצף B מ-0 ועד האות j. הטבלה מוגדרת על פי הבסיס:

<math>
F_i0 = 0,\; 0\le i\le m
</math>

<math>
F_0j = 0,\; 0\le j\le n
</math>

<math>
\text{ if } a_i = b_j
</math> then
<math>
w(a_i, b_j) = w\text{(match)}
</math>
<math>
\text{ or if } a_i \neq b_j
</math> then
<math>
w(a_i, b_j) = w\text{(mismatch)}
</math>

<math>F_{ij} = \max \begin{Bmatrix}
0 \\
F_{i-1,j-1}+ \ w(a_i,b_j) & \text{Match/Mismatch} \\
F_{i-1,j} + \ w(a_i,-) & \text{Deletion} \\
F_{i,j-1} + \ w(-,b_j) & \text{Insertion}
\end{Bmatrix}
,\; 1\le i\le m, 1\le j\le n
</math>

כאשר:
* <math>m = \text{length}(a)</math>
* <math>n = \text{length}(b)</math>
* <math>w(c,d),\; c, d\in\Sigma\cup\{'-'\}</math> - ציון להחלפה, כאשר '–' הוא מציין רווח

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

== ראו גם ==
* [[Multiple sequence alignment]]
* [[אנליזת ריצוף - Bowtie]]

==לקריאה נוספת==
<div class="mw-content-ltr">
*Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison (1999). ''Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids''. Cambridge University Press. {{ISBN|0-521-62971-3}}.
</div>
==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{בקרת זהויות}}
[[קטגוריה:ביואינפורמטיקה]]
[[קטגוריה:מחרוזת (מדעי המחשב)]]