Closest string matching

การค้นหาสายอักขระที่ใกล้เคียงกันที่สุด

Name: Tanachai Pathomrat

LCSH: Algorithms

LCSH: Permutations

LCSH: String

Abstract: The problem of finding a center string that is close to every given string is called the closest string problem. This problem is defined as: Given a set of strings S={s1,s2,…,sn} each of length m, the problem is to find the smallest d and a string s of length m, which is within Hamming distance d to each si ∈ S. The problem arises in computational molecular biology in identifying genetic drug and generating genetic probes. This thesis proposed an algorithm to solve the closest string problem. The algorithm starts with generating all possible permuted strings of length m. Then, it eliminates strings which are not candidate solutions using many elimination rules. Next, Hamming distances are calculated and compared. Then, the best solutions are finally selected. Three versions of the proposed algorithm have been developed: Finding Closest String Matching Using Array (FCMA), Finding Closest String Matching Using Text File (FCMT) and Finding Closest String Matching Using Database File (FCMD). All of them process in a similar manner, except the storage devices and programming techniques used. FMCA uses only main memory, so it can run faster but it’s suitable for small problems. FCMT and FCMD use a secondary storage device to store an enormous number of permuted strings. They can solve larger problems with slower processing time. From the experiments, we found that the proposed algorithm can run in very much less than exponential time. All three versions of the proposed algorithm can find all exact solutions in all cases of m, n ≤ 20 with reasonable processing time. We also investigated and compared with similar applications currently in use called, BLAST and FASTA. However, a direct comparison can not be performed.

Abstract: ปัญหาในการหาสายอักขระที่ใกล้เคียงกันที่สุดกับเซตของ string ที่กำหนดให้ เราเรียกว่า The Closest String Problem ปัญหาดังกล่าวจะกำหนดกลุ่มของสายอักขระ ที่ประกอบด้วยเซตของสาย อักขระ S={s1,s2,…,sn} โดยแต่ละสายอักขระ มีความยาว m ซึ่งการแก้ไขปัญหาดังกล่าวจะหาค่า Hamming Distance ที่น้อยที่สุด d และสายอักขระ s ที่มีความยาว m โดยที่ Hamming Distance ระหว่าง s กับ si ∈ S ไม่เกิน d ปัญหาดังกล่าวได้ถูกนำไปใช้ในงานด้านชีวสารสนเทศ เกี่ยวกับการ identify genetic drug และ generating genetic probes งานวิจัยนี้ได้นำเสนอวิธีการแก้ไขปัญหาของการหาการค้นหาสายอักขระ s โดยเริ่มต้นจากการ generate การจัดลำดับของสายอักขระที่มีความยาว m ด้วยวิธีของ Permutation จากนั้นจะกำจัดสายอักขระ ที่ไม่ใช้คำตอบออกไป เพื่อลดจำนวนสายอักขระ โดยการใช้กฎเกณฑ์ต่าง ๆ หลังจากนั้นจะนำไปคำนวณหา Hamming Distance กับสายอักขระที่กำหนดให้, si, และเปรียบเทียบหาสายอักขระที่ใกล้เคียงกันที่สุด โดย งานวิจัยนี้ได้นำเสนอ 3 วิธีการคือ Finding Closest String Matching Using Array (FCMA), Finding Closest String Matching Using Text File (FCMT) และ Finding Closest String Matching Using Database File (FCMD) ทั้ง 3 วิธีการค้นหาดังกล่าว ดำเนินการในลักษณะที่คล้ายกัน จะแตกต่างกันที่สื่อในการจัดเก็บข้อมูล และเทคนิคการเขียนโปรแกรม โดยที่ FCMA จะใช้หน่วยความจำใน main memory อย่างเดียว ซึ่งจะทำงานเร็วกว่าวิธีการอื่น ๆ แต่เหมาะกับการแก้ไขปัญหาขนาดเล็ก ส่วน FCMT และ FCMD จะใช้ main memory ร่วมกับการเก็บผลลัพธ์ในสื่อบันทึกข้อมูลทุติยภูมิ ซึ่งสามารถ แก้ไขปัญหาขนาดใหญ่ได้แต่ใช้เวลาในการค้นหาช้ากว่า จากการทดลองเราพบว่า algorithm ที่นำเสนอ สามารถทำงานได้ ในเวลาที่น้อยกว่า exponential time มาก ซึ่งสามารถค้นหา exact solution ได้ใน ความยาว สำหรับ m, n ≤ 20 นอกจากนี้ ยังได้ตรวจสอบโปรแกรมที่ใช้อยู่ในปัจจุบันที่เรียกว่า BLAST และ FASTA เพื่อทำการเปรียบเทียบ แต่อย่างไรก็ตามการเปรียบเทียบโดยตรงไม่สามารถจะทำได้

Mahidol University

Address: NAKHON PATHOM

Email: liwww@mahidol.ac.th

Name: Damras Wongsawang

Role: Thesis Advisors

Created: 2003

Modified: 2553-02-08

Issued: 2009-12-25

วิทยานิพนธ์/Thesis

application/pdf

ISBN: 9740438059

CallNumber: TH T161c 2003

eng

DegreeName: Master of Science

Level: Master's Degree

Descipline: Computer Science

Grantor: Mahidol University

©copyrights Mahidol University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	4137845.pdf	1.62 MB	38	2019-12-18 14:47:32

ใช้เวลา

0.342658 วินาที