נושא הפרוייקט
מספר פרוייקט
מחלקה
שמות סטודנטים
אימייל
שמות מנחים
קידוד עבור מערכות אחסון מבוססות דנ"א
Coding for DNA based storage media
תקציר בעיברית
בעולם המודרני קיימת בעיה הולכת וגדלה של אחסון מידע דיגיטלי, כמות המידע המאוחסן בשרתים כיום הינו עשרות זטה-בתים ומספר זה צפוי לגדול בצורה אקספוננציאלית. כמות זו צפויה בעתיד שמירה של הכמות האדירה של המידע הדיגיטלי הנ"ל בחוות שרתים כפי שנהוג כיום תוביל לצריכה לא סבירה של אנרגיה ומרחב פיזי, על מנת להימנע מכך חוקרים וחברות רבות בוחנים שיטות חדשות לאחסון של מידע דיגיטלי שיטה אחת אשר מראה פוטנציאל גבוה במיוחד הינה אחסון של המידע על מולקולות של דנ"א, הדנ"א הינה מולקולה יציבה מאד אשר בעזרת ארבעה אותיות המסמלות את ארבעת המרכיבים המולקולריים האפשריים מסוגלת להצפין על גבייה כמות גדולה של מידע תוך שימוש במעט מרחב פיזי שיטה זו מציעה שפע של יתרונות אך איתם גם אתגרים חדשים, אחד מאותם האתגרים ידוע כ"בעיית הקריאה" ונוגע לשגיאות בעת קריאת המידע, ובו עוסק המחקר. בעיית הקריאה הינה תוצר של המגבלה על אורך הרצף אותו הטכנולוגיה הקיימת כיום מסוגלת לקרוא בלי טעויות, כאשר רצפים ארוכים של מידע דיגיטלי לא עומדים בהגבלה זו, ועל כן בעת הקריאה המולקולה מחולקת לתת רצפים קצרים יותר הנקראים קריאות אותם ניתן לקרוא ולקודד חזרה לבינארי, אך בכדי לשחזר את המידע יש להרכיב את הרצף המלא מאותן קריאות קצרות במהלך תהליך הקריאה מקטעים חוזרים ברצף גורמים לאי ודאות בהרכבה ותורמים רבות לאחוזי שגיאה גבוהים לצורך פתרון הבעיה, הוצע אלגוריתם לקידוד מקדים של האינפורמציה המורכב משני חלקים, המקודד מוחק את החזרות הבעייתיות תוך שמירת מידע שיאפשר שחזור של הרצף המקורי בסוף הקריאה, רצף המוצא של המקודד יתורגם לדנ"א ובכך נבטיח את הרכבת הרצף בחזרה מחלקיו הקצרים בעת הקריאה. המשחזר מקבל את תוצר ההרכבה המקודד ומשחזר ממנו את המידע המקורי בעזרת המידע שנשמר במהלך הקידוד. המידע המקודד על המולקולה עובר תהליך נוסף לפני כן, בו בעזרת אלגוריתם המבוסס על מערכות מאולצות, נמחקות חזרות של חלונות באורך המתאים תוך שמירת מידע שיאפשר שחזור של המידע המקורי בעת הקריאה, הרצף שאלגוריתם זה מספק יקודד לדנ"א ובכך נבטיח את הרכבת הרצף בחזרה מחלקיו הקצרים בעת הקריאה. בפרויקט זה מימשתי בשפת פייטון את האלגוריתם כפי שהוצע במאמר עליו הפרויקט מבוסס, תוך שימת דגש על יעילות חיפוש וקיצור זמני ריצה. אופיו הדינאמי של חיפוש החזרות ושל הרצף עצמו במהלך הקידוד מובילים לחיפוש מאתגר עם סיבוכיות גבוהה במיוחד, כאשר סכמת חיפוש נאיבית מובילה לזמני ריצה ארוכים מאד בפרט עבור רצפים ארוכים. בכדי לקצר ככל הניתן את זמני הריצה בחנתי מספר אלגוריתמים לחיפוש יעיל וביצעתי השוואה למציאת היעיל ביותר. בכדי לבחון את המימוש בדקתי את דיוק השחזור של רצפים אקראיים באורכים שונים ועבור כולם התקבלו 0% שגיאות בשחזור.
תקציר באנגלית
In a world with ever growing data storage needs, the capacity of traditional technologies is expected to be exceeded in the next few decades motivating many researchers to seek Innovative alternatives. An especially promising possibility is DNA based storage, DNA is a highly durable molecule which uses a quaternary alphabet (A, C, T, G) to encode large amounts of information in a very small space and requires little to no maintenance aside from climate control. Despite its great potential, DNA based storage systems are a long way from being practical for commercial scale use due in large part to high error rates during the reading process, this problem is known as “the read problem”. One of the major contributors to the error rate is the presence of repetitions within the data string, giving rise to a need for an encoding scheme that eliminates repetitions in a way that ensures the data is uniquely reconstructible. In this project I have implemented such encoding-decoding scheme as was proposed in the article “Repeat Free Codes” by O. Elishco, E. Yaakobi, R. Gabrys and M. Medard. the Algorithm is comprised of two complementary parts, the encoder and the decoder. The encoder searches for repetition of a given length and deletes them as well as adding information about the deletion for future recovery, and the decoder receives the reconstructed encoded string and reverses the encoding process, using the information saved by the encoder. Due to the dynamic nature of the encoder, the search for repetitions is extremely computationally heavy for long input strings. Therefore, I have emphasized the time efficiency of the search as I tested and compared the performance of different search algorithms to minimize the run time. To test my implementation, I have examined the accuracy of the reconstruction of randomly generated sequences in various lengths, which yielded a consistent 0% Bit Error Rate. Key words: the read problem, repetitions, uniquely reconstructible, Repeat Free Codes, encoder, decoder, time efficiency, search algorithms