עבור לתוכן

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

Featured Replies

פורסם

שלום,

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

הגדרה:

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

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

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

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

הבעיה:

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

דוגמה:

ababcABCDddCRTYYEdd

ABCDfdabcCRTYYEeabc

abCRTYYEABCDrtyyydabc

ה-MUMים כאן הם:

1. ABCD

2. CRTYYE

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

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

תודה מראש,

אלי

eliahninyo@hotmail.com

פורסם

התועיל בטובך לומר מה זה SUFFIX TREE ?

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

ארכיון

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

דיונים חדשים