Chulalongkorn University Theses and Dissertations (Chula ETD)

ระบบการประมวลผลเชิงขนานสำหรับโปรแกรมบลาสท์

Other Title (Parallel Title in Other Language of ETD)

A parallel processing system for a BLAST program

Year (A.D.)

2002

Document Type

Thesis

First Advisor

ประภาส จงสถิตย์วัฒนา

Second Advisor

ณัฐวุฒิ หนูไพโรจน์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2002.1218

Abstract

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

Other Abstract (Other language abstract of ETD)

BLAST (Basic Local Alignment Search Tool) is one of the most widely used search tools, which identifies statistically significant matches between newly sequenced segments of genetic material or proteins and databases of known nucleotide or amino acid sequences. Such searches allow scientists to make inferences about the structures and functions of their discoveries or to screen new sequences for further investigation. Although BLAST has been designed and optimized for speed, the major drawback of BLAST is that it consumes large amount of CPU-time, memory, and I/O. It takes a very long time to search a large number of queries in a large database. Preliminary study of BLAST indicates that BLAST's running time is proportional to the size of the database. BLAST shows the highest efficiency if the whole database can be fitted in the memory. As the genome databases are enormous and doubling in size every 1.3 years, it is important to improve the performance in the limited main memory environment. This thesis proposes to separate the database into smaller parts, which each part fits the available memory and then search each part separately in each node of a parallel system. The implemented system can eliminate swapping time as shown in the result of superlinear speedup.

Link to Full Text

Share

COinS