Multiple sequence alignment
MSA - Multiple sequence alignment הוא עימוד של שלושה או יותר רצפים ביולוגיים, כדוגמת DNA ,RNA או חלבון. במקרים רבים, הקלט להגדרת רצפי שאילתא מניח שיש קשר אבולוציוני שבו הם חולקים את השושלת וצאצאים של אב קדמון משותף. ניתן לבצע ניתוח פילוגנטי כדי להעריך מקורות אבולוציוניים המשותפים של הרצפים.
תיאורים ויזואליים של רצפי המולקולות ממחישים אירועי מוטציה כגון מוטציה נקודתית (חומצת אמינו אחת או שינויי נוקלאוטידים) המופיעה כאותיות שונות בעמודה אחת בעימוד, ומוטציות החדרה או מחיקה (indels או פערים) המופיעות כמקפים באחד או יותר מהרצפים בעימוד.
עימוד רצפים מרובה משמש לעיתים קרובות כדי להעריך את שימור רצף של חומצות האמינו בחלבונים ונוקלאוטידים בחומר התורשתי.
עימוד מספר רצפים דורש שיטות מתוחכמות יותר מעימוד רצפים פשוט של שתי מחרוזות שכן הוא מסובך יותר חישובית. רוב התוכנות העושות עימוד מרובה רצפים עושות שימוש בשיטות היוריסטיות ולא בהכרח מוצאות את האופטימום הגלובלי. גישה ישירה לבעיה יכולה להיעשות באמצעות תכנון דינמי למציאת עימוד אופטימלי גלובלית, בדומה לעימוד רצפים פשוט - אולם לצורך עימוד N רצפים נדרש מילוי של מטריצה הכרוך ב-. קיימות גישות להגבלה ולצמצום מרחב החיפוש בתכנון הדינמי, למשל עימוד מקדים של כל זוג רצפים בעימוד רצפים פשוט. אחת הגישות הנפוצות ביותר להתמודדות עם הבעיה היא חיפוש היוריסטי בשיטת התקדמות (או שיטה היררכית או שיטת עץ): באמצעות שימוש תחילה בזוג הרצפים הדומה ביותר בכל שלב. גישה זו נמצאת בשימוש בכלי הפופולרי Clustal. קיימות גישות איטרטיביות, הדומות לחיפוש בשיטת התקדמות, אך מאפשרות לבחון מחדש רצפים ששולבו בעימוד - כך עשוי להתקבל עימוד טוב יותר, במחיר של זמן ריצה ארוך יותר. גישה נוספת לעימוד רצפים מרובה היא שימוש במודל מרקוב חבוי (HMM) - באמצעות מודל משערכים הסתברות לעימודים שונים, וניתן לבחור את העימודים שלהם הנראות המקסימלית.
