למומחים בלבד (במציאת אלגוריתם): MUMs ב-Suffix Tree - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

למומחים בלבד (במציאת אלגוריתם): MUMs ב-Suffix Tree


eninyo

Recommended Posts

שלום,

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

הגדרה:

תת מחרוזת נקראת MUM אם:

1. היא מופיע בכל אחת ממחרוזות הקלט.

2. היא מופיע בכל אחת מהן בדיוק פעם אחת.

3. אין תת מחרוזת אחרת המכילה אותה ומקיימת את תכונה 1+2.

הבעיה:

בהינתן קבוצת גנומים ( מחרוזות תווים ארוכות מאוד שהא"ב שלהם מוגבל בדר"כ ל-4 אותיות), צריך למצוא את הMUMים תוך שימוש בsuffix tree.

דוגמה:

ababcABCDddCRTYYEdd

ABCDfdabcCRTYYEeabc

abCRTYYEABCDrtyyydabc

ה-MUMים כאן הם:

1. ABCD

2. CRTYYE

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

מקווה שמישהו הבין את הבעיה.

תודה מראש,

אלי

eliahninyo@hotmail.com

קישור לתוכן
שתף באתרים אחרים

  • 2 שבועות מאוחר יותר...

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

×
  • צור חדש...