Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

BLAST Local Alignment Algorithm คืออะไร?


อัลกอริธึม BLAST ผลิตโดย Altschul, Gish, Miller ประมาณปี 1990 ที่ศูนย์ข้อมูลเทคโนโลยีชีวภาพแห่งชาติ (NCBI) BLAST ใช้เพื่อให้ได้มาซึ่งความสัมพันธ์เชิงหน้าที่และวิวัฒนาการระหว่างลำดับต่างๆ และเพื่อช่วยให้รู้จักสมาชิกของตระกูลยีน

เว็บไซต์ NCBI มีฐานข้อมูล BLAST ทั่วไปหลายฐานข้อมูล ตามเนื้อหาจะรวมกันเป็นฐานข้อมูลนิวคลีโอไทด์และโปรตีน NCBI ยังสนับสนุนฐานข้อมูล BLAST เฉพาะทาง รวมถึงฐานข้อมูลการคัดกรองเวกเตอร์ มีฐานข้อมูลจีโนมหลายฐานข้อมูลสำหรับสิ่งมีชีวิตหลายชนิด และติดตามฐานข้อมูล

BLAST ใช้วิธีฮิวริสติกเพื่อค้นหาการจัดตำแหน่งภายในที่ใหญ่ที่สุดระหว่างลำดับการสืบค้นและฐานข้อมูล BLAST เพิ่มความเร็วในการค้นหาโดยสมบูรณ์โดยแบ่งลำดับที่จะเปรียบเทียบเป็นลำดับของส่วนย่อย (กำหนดเป็นคำ) และค้นหาการจับคู่ระหว่างคำเหล่านี้ในขั้นต้น

ใน BLAST คำเหล่านี้ถือเป็น k-tuples สำหรับดีเอ็นเอนิวคลีโอไทด์ คำหนึ่งโดยทั่วไปประกอบด้วย 11 เบส (นิวคลีโอไทด์) ในขณะที่โปรตีน คำหนึ่งโดยทั่วไปประกอบด้วยกรดอะมิโน 3 ตัว BLAST สร้างตารางแฮชของคำในละแวกใกล้เคียง (เช่น เกือบตรงกัน) ในขณะที่กำหนดเกณฑ์สำหรับ "ความใกล้ชิด" จะขึ้นอยู่กับสถิติ เริ่มจากการจับคู่แบบตรงทั้งหมดจนถึงคำในละแวกใกล้เคียง

เนื่องจากการจัดตำแหน่งที่ดีต้องมีการจับคู่ที่ใกล้เคียงหลายรายการ จึงสามารถใช้สถิติในการตัดสินว่าการจับคู่ใดมีความสำคัญ ด้วยการแฮช มันสามารถค้นหาการแข่งขันในเวลา O (n)(เชิงเส้น) การเข้าถึงคู่ที่ตรงกันในทั้งสองทิศทาง วิธีการค้นพบการจัดตำแหน่งคุณภาพสูงรวมถึงคู่ที่ได้คะแนนสูงสุดและคู่ส่วนสูงสุดหลายคู่

มีหลายเวอร์ชันและส่วนขยายของอัลกอริธึม BLAST ตัวอย่างเช่น สามารถใช้ MEGABLAST, MEGABLAST ที่ไม่ต่อเนื่อง และ BLASTN เพื่อจดจำลำดับนิวคลีโอไทด์ได้ MEGABLAST ได้รับการออกแบบมาโดยเฉพาะเพื่อค้นหาการจัดตำแหน่งที่ยาวระหว่างลำดับเดียวกันอย่างมีประสิทธิภาพ ดังนั้นจึงเป็นอุปกรณ์ที่ดีที่สุดในการค้นหาการจับคู่ที่เหมือนกันกับลำดับการสืบค้น

พารามิเตอร์สำคัญประการหนึ่งที่ชี้แนะความไวของการค้นหา BLAST คือความยาวของคำต้นฉบับหรือขนาดคำ ขนาดคำมีความยืดหยุ่นใน BLASTN และสามารถลดจากค่าเริ่มต้นเป็นขั้นต่ำ 7 เพื่อปรับปรุงความไวในการค้นหา ดังนั้น BLASTN จึงเหนือกว่า MEGABLAST ในการค้นพบการเรียงตัวของลำดับนิวคลีโอไทด์ที่เกี่ยวข้องจากสิ่งมีชีวิตต่างๆ

โปรตีน-โปรตีน BLAST มาตรฐาน (BLASTP) ใช้สำหรับทั้งการจดจำลำดับกรดอะมิโนของแบบสอบถามและสำหรับการค้นหาลำดับเดียวกันในฐานข้อมูลโปรตีน Position-Specific Iterated (PSI)-BLAST ถูกสร้างขึ้นสำหรับการค้นหาความคล้ายคลึงของโปรตีนที่มีความไวสูง เป็นประโยชน์สำหรับการค้นพบโปรตีนที่เกี่ยวข้องกันอย่างมาก

Pattern-Hit Initiated (PHI)-BLAST สามารถค้นหารูปแบบโปรตีนที่จำกัดได้ สร้างขึ้นเพื่อค้นหาโปรตีนที่มีรูปแบบที่กำหนดโดยผู้ใช้และเหมือนกันกับลำดับการค้นหาในบริเวณใกล้เคียงกับรูปแบบ