ד"ר ריבה שלום בכנס בינלאומי בקופנהגן

מחקר משותף בהובלת ד"ר ריבה שלום הוצג בכנס בינלאומי מוביל במדעי המחשב

מאמר פרי מחקר משותף של ד"ר ריבה שלום מהמחלקה להנדסת תוכנה, יחד עם חוקרים מהמחלקות למדעי המחשב באוניברסיטת אריאל ובאוניברסיטת בר־אילן, הוצג בכנס הבינלאומי 37th Annual Combinatorial Pattern Matching (CPM) Conference, שהתקיים במהלך חודש יוני בקופנהגן, דנמרק.

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

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

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