چکیده:
ساختار داده ابزاری برای ذخیره و بازیابی بوده و به طور کلی، روش منطقی و ریاضی یک سازماندهی خاص از داده ها نامیده می شود. کشف توالی های مختلف ژنوم و پروتئین در جانداران مختلف نیاز به نمایه سازی آن و نوع ساختار داده متناسب، در جهت بازیابی سریعتر را افزایش داده است. ساختارهای داده رشته ای در طول سال های اخیر پرکاربردترین ساختارهای داده نمایه سازی ژنوم بوده است. به لحاظ روش پژوهش این مقاله حاضر مروری بوده و با بررسی مقالات مختلف مرتبط، سه نوع ساختار داده نمایه سازی پایگاههای ژنوم از جمله رشته ای، درخت پسوندی، آرایه پسوندی و نمودار مارپیچ مستقیم کلمه را معرفی می نماید. نتایج پژوهش نشان می دهد که درخت پسوندی و نمودار مارپیچ مستقیم کلمه ساختارهایی با حجم بالا و آرایه پسوندی حجم کمتری را در حافظه اشغال می کنند. درخت پسوندی و نمودار مارپیچ مستقیم کلمه، نسبتا پویا بوده اما آرایه پسوندی ساختاری مرتب شده بوده و تغیر داده ها در این ساختار به سختی صورت می گیرد. آرایه پسوندی می تواند بر روی حافظه های جانبی ذخیره پیاده سازی شود با وجود اینکه بازیابی داده ها در آن به کندی صورت می گیرد. اما در مورد نمودار مارپیچ مستقیم کلمه امکان ذخیره سازی در حافظه جانبی امکان نداشته و درخت های پسوندی نیز ناکارآمد می باشد.
Data structure is a tool for storage and retrieval of information which is named logic and mathematic way of specific data organization. various sequences of genes and proteins in various creatures increases the amount of data in genome databases, and finding appropriate data structure and indexing are subject for many studies. String data structures are general data structure for genome indexing, and this article would review the many used three types of string data structure, suffix tree, suffix array, and Directed Acyclic Word Graphs. This paper is a review of the literature related to three types of data, including genome databases indexing field, tree, postfix, postfix and graphs spiral array directly introduces the word. Findings of this research show that suffix tree and Directed Acyclic Word Graph (DAWG) structures need much space however suffix array need less space. Against the Directed Acyclic Word Graph, suffix array can be stored on Memory Stick. Suffix tree and Directed Acyclic Word Graph are a dynamic structures but as suffix array is a Sorted out structure, it could hardly be changed.
خلاصه ماشینی:
به لحاظ روش پژوهش ، اين مقاله مـروري بـوده و بـا بررسـي مقـالات مختلـف مرتبط ، سه نوع سـاختار داده نمايـه سـازي پايگـاه هـاي ژنـوم از جملـه رشـته اي ، درخت پسوندي ، آرايۀ پسوندي و نمودار مارپيچ مستقيم کلمه معرفي مي شود.
data structure 582 داراي در حدود ٣ بيليون جفت نوکلئوتيد بـوده و پايگـاه هـاي اطلاعـات ژنـوم انسـاني بـيش از ١٥ بيليون جفت نوکلئوتيد را در بر گرفته است و براي ذخيره سـازي آن ٤٥ گيگابايـت حافظـه صـرف خواهد شد (١ ,٢٠٠١ Shibuya &Sadakane ).
بيشتر پژوهش هاي اين حوزه عبارت انـد از: تطبيق ٢ و مقايسۀ توالي هاي ژن و پـروتئين در داخـل يـک گونـه و يـا بـين گونـه هـاي مختلـف جانداران که ارتباط بين گونه هاي مختلف جانداران را مشخص کرده و رونـد تکـاملي آنهـا را نشان مي دهد؛ ̄ يافتن ژن خاص و بازيابي نظير به نظير رشتۀ مورد نظر از طريق رونويسي آراِنِ اي ٣ از ژن ( Sung ٢٠٠٥)؛ تطبيق توالي هاي کوچک ژن و اتصال آنها و تشکيل ژنوم کامل ؛ پيش بيني ساختارهاي پروتئيني و تجلي هاي ژن ٤ ناشناخته با بررسـي شـباهت تـوالي هـاي آن بـا توالي هاي ژن هايي با عملکرد مشخص (٢٠٠٧ Bioinformatic).
ساختارهاي داده مناسب پايگاه هاي اطلاعاتي ژنوم معروف ترين ساختار دادة متن مورد اسـتفاده در موتورهـاي کـاوش و پايگـاه هـاي اطلاعـاتي متون که به دليل پويايي و حجم پايين ، کاربرد زيادي دارند، نمايه مقلوب ١ و يا فايل مقلوب هستند 2 (٢٠٠٥ Turpin &Puglisi, Smyth, )٣.
ساختارهاي تمام متن مانند آرايۀ پسوندي ، درخت پسوندي و گراف مارپيچ مسـتقيم کلمـه از جمله ساختار داده هاي ارائه شده براي حل اين مشکل هستند.