การศึกษาการจับคู่เหมือนของสตริงย่อยในฐานข้อมูลขนาดใหญ่

ชื่อผู้จัดทำโครงงานวิทยาศาสตร์
  • ชัชวาล วัชรมโนธรรม

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
  • จารุโลจน์ จงสถิตย์วัฒนา

สถาบันการศึกษาที่กำกับดูแลโครงงานวิทยาศาสตร์

ภาควิชาคณิตศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย

ระดับการศึกษา

โครงงานในระดับการศึกษาปริญญาโทขึ้นไป

หมวดวิชา

โครงงานในสาขาวิชาคอมพิวเตอร์

วันที่จัดทำโครงงานวิทยาศาสตร์

01 มกราคม 2541

บทคัดย่อโครงงานวิทยาศาสตร์

โครงงานนี้มุ่งศึกษาวิธีการค้นหาแบบช่วงโดยประมาณสำหรับสายอักขระย่อยในฐานข้อมูลจีโนมโดยการกำจัดสายอักขระที่ไม่คล้ายคลึงออกก่อนที่จะใช้ขั้นตอนวิธีที่ใช้ทรัพยากรมาก ในการค้นหาแบบช่วงผู้ใช้จะให้คำค้นหาเป็นสายอักขระและระยะห่าง เครื่องจะต้องทำการค้นหาสายอักขระย่อยในฐานข้อมูลที่มีความคล้ายกับคำค้นหาในระยะที่กำหนด การค้นหาโดยประมาณใช้โครงสร้างของดัชนีซึ่งสร้างจากความถี่ของสัญลักษณ์ที่ปรากฏในสายอักขระ เนื่องจากสายอักขระที่ค้นหาอาจมีความยาวต่างกัน จึงได้สร้างโครงสร้างของ ดัชนีจากสายอักขระย่อยที่มีความยาวแตกต่างกัน โครงสร้างของดัชนีเหล่านี้ได้ถูกใช้ในการกำจัดสตริงย่อยที่ห่างจากคำค้นหามากกว่าระยะที่กำหนด โดยเริ่มจากดัชนีที่สร้างสำหรับสตริงย่อยที่สั้นที่สุด สุดท้ายนี้เราได้สร้างเครื่องมือสำหรับการค้นหาแบบช่วงโดยประมาณสำหรับฐานข้อมูลจีโนม

This project studies a method to approximate range queries for substring in genomic databases, by eliminating some irrelevant substrings before using a more costly algorithm. In a range query, a query string and a distance are given, and we need to find a set of substrings in the database which are not different from the query string by more than a given distance. The query approximation is based on an index structure created from the frequency of symbols in each string. Since the query string can be of any arbitrary length, a number of index structures are created from substrings of different lengths. Then, these index structures are used to eliminate some substrings, starting from the index created from shortest substrings, which are further away from the query string by more a the given distance. Finally, a query tool is implemented for the approximate range query on genomic databases.