ساختارهای داده نمایه سازی و توالی های ژنوم و پروتئینی

نویسنده

دانشگاه شیراز

10.35050/JIPM010.2016.047

چکیده

ساختار داده ابزاری برای ذخیره و بازیابی بوده و به طور کلی، روش منطقی و ریاضی یک سازماندهی خاص از داده ها نامیده می شود. کشف توالی های مختلف ژنوم و پروتئین در جانداران مختلف نیاز به نمایه سازی آن و نوع ساختار داده متناسب، در جهت بازیابی سریعتر را افزایش داده است. ساختارهای داده رشته ای در طول سال های اخیر پرکاربردترین ساختارهای داده نمایه سازی ژنوم بوده است. به لحاظ روش پژوهش این مقاله حاضر مروری بوده و با بررسی مقالات مختلف مرتبط، سه نوع ساختار داده نمایه سازی پایگاههای ژنوم از جمله رشته ای، درخت پسوندی، آرایه پسوندی و نمودار مارپیچ مستقیم کلمه را معرفی می نماید. نتایج پژوهش نشان می دهد که درخت پسوندی و نمودار مارپیچ مستقیم کلمه ساختارهایی با حجم بالا و آرایه پسوندی حجم کمتری را در حافظه اشغال می کنند. درخت پسوندی و نمودار مارپیچ مستقیم کلمه، نسبتا پویا بوده اما آرایه پسوندی ساختاری مرتب شده بوده و تغیر داده ها در این ساختار به سختی صورت می گیرد. آرایه پسوندی می تواند بر روی حافظه های جانبی ذخیره پیاده سازی شود با وجود اینکه بازیابی داده ها در آن به کندی صورت می گیرد. اما در مورد نمودار مارپیچ مستقیم کلمه امکان ذخیره سازی در حافظه جانبی امکان نداشته و درخت های پسوندی نیز ناکارآمد می باشد.

کلیدواژه‌ها


عنوان مقاله [English]

Data structures of genome and protein sequences indexing

نویسنده [English]

  • Adeleh asadi
چکیده [English]

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.

کلیدواژه‌ها [English]

  • data structure
  • Genome
  • Indexing
  • suffix tree
  • suffix array
  • Directed Acyclic Word Graphs
  • inverted file