נושא הפרוייקט
מספר פרוייקט
מחלקה
שמות סטודנטים
אימייל
שמות מנחים
אלגוריתם לחיפוש מטרות-חוץ של CRISPR בגנום
CRISPR Genome off-target search algorithm
תקציר בעיברית
CRISPR היא שיטה נפוצה לעריכת גנים. לCRISPR יש דיוק גבוה באתר המטרה המיועדת אך עלול לערוך בתהליך, באופן בלתי רצוי, אתרי מטרות-חוץ. הדימון בין אתרי מטרות החוץ לאתר המטרה נמדד על ידי מרחק עריכה. מרחק עריכה הוא מספר הפעולות המינימלי (הכנסה, מחיקה או החלפה) כדי להשוות בין מחרוזת אחת לשנייה. המטרה שלנו היא לפתח אלגוריתם שמוצא את כל אתרי מטרות-חוץ בגנום נתון תוך כדי שיפור בזמן הריצה בהשוואה לשיטות הקיימות ומתן אפשרות להפרדה בין ספי פעולות העריכה. BitOffinder, השיטה שלנו, כללה שני שלבים. השלב הראשון כלל יישום אלגוריתם Gen-ASM למעבר על הגנום ואיתור מטרות-חוץ פוטנציאליות העומדות במרחק עריכה נתון. השלב השני כלל פיתוח ויישום אלגוריתם מעקב מבוסס תכנון דינאמי למציאת העמדה מסוימת העומדת בסף העריכה לכל פעולה הנתון. אנו מראים בתוצאות שלנו ש-BitOffinder מאתר במדיוק את כל מטרות החוץ, בצורה מדויקת ואמינה בזמן ריצה נמוך משמעותית מהשיטה האמינה ביותר שקיימת כיום (CALITAS), תוך תמיכה במאפיינים שונים. BitOffinder מספק חלופה מצוינת לשיטות הקיימות, תוך מציאת כל אתרי מטרות החוץ בצורה מדויקת והפחתה משמעותית בזמן הריצה. מילות מפתח: מרחק עריכה, מטרות-חוץ ,העמדת רצפים, השוואת מחרוזות, עריכה גנטית, אלגוריתם, CRISPR, Bitap, תכנות דינאמי.
תקציר באנגלית
CRISPR is a common method for gene editing. CRISPR has high precision at the target site but may unintentionally edit similar off-target sites in the process. Off-target similarity to the target can be measured by the edit-distance metric. The Edit Distance is the minimum number of operations (i.e., insertion, deletion, and substitution) to transform one string to the other. Our goal is to develop an algorithm that finds all potential off-target sites in a given genome, with improvement in runtime compared to existing methods and enabling a specific threshold per edit operation. BitOffinder, our approach, includes two steps. First, we implemented the GenASM algorithm that traverses the genome and identifies potential off-target sites up to a given edit distance. Second, we developed a dynamic-programming-based trace-back algorithm to check if there is an alignment that satisfies the given operation thresholds. We show in our results that BitOffinder accurately identifies all off-target sites, while significantly reducing the runtime compared to an existing method (CALITAS) while supporting various features. BitOffinder provides an excellent alternative to existing methods, accurately identifying all off-target sites while significantly reducing runtime. Keywords: Edit distance, Off-target, Sequence alignment, string-matching, Genetic editing, Algorithm, CRISPR, Bitap, Dynamic programing.