วิกิพีเดียภาษาไทย
กลับไปหน้าบทความ

อ่าน 18 นาที

ไม่มีชื่อบทความ

ใน ภาษาศาสตร์เชิงทฤษฎี และ ภาษาศาสตร์เชิง คำนวณ ไวยากรณ์บริบทอิสระเชิงความน่าจะเป็น ( PCFGs ) เป็นส่วนขยาย ของไวยากรณ์บริบทอิสระ คล้ายกับที่ แบบจำลองมาร์คอฟแบบซ่อน เร้นขยาย...

ไวยากรณ์แบบไร้บริบทเชิงความน่าจะเป็น

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

PCFG (Programmable Functional Formatting Group) มีต้นกำเนิดมาจากทฤษฎีไวยากรณ์และมีการประยุกต์ใช้ในหลากหลายสาขา ตั้งแต่การประมวลผลภาษาธรรมชาติไปจนถึงการศึกษาโครงสร้างของ โมเลกุล RNAและการออกแบบภาษาโปรแกรมการออกแบบ PCFG ที่มีประสิทธิภาพต้องคำนึงถึงปัจจัยด้านความสามารถในการขยายขนาดและความเป็นสากล ปัญหาต่างๆ เช่น ความกำกวมของไวยากรณ์จะต้องได้รับการแก้ไข การออกแบบไวยากรณ์ส่งผลต่อความถูกต้องของผลลัพธ์ อัลกอริทึมการวิเคราะห์ไวยากรณ์มีความต้องการด้านเวลาและหน่วยความจำที่แตกต่างกัน

คำจำกัดความ

การสร้างสตริงแบบวน ซ้ำ: กระบวนการสร้างสตริงจากไวยากรณ์โดยใช้ การเรียกซ้ำ

การแยกวิเคราะห์ :การค้นหาโครงสร้างประโยคที่ถูกต้องโดยใช้ออโตมาตอน

แผนผังการวิเคราะห์ ไวยากรณ์ (Parse Tree):การจัดเรียงไวยากรณ์ให้สอดคล้องกับลำดับของข้อมูล

ตัวอย่างหนึ่งของตัวแยกวิเคราะห์สำหรับไวยากรณ์ PCFG คือออโตมาตาแบบพุชดาวน์ อัลกอริทึมนี้แยกวิเคราะห์เอ็นเทนเมนต์ของไวยากรณ์จากซ้ายไปขวาใน ลักษณะ คล้ายสแต็ก วิธีการแบบ ใช้กำลังทั้งหมดนี้ไม่ได้มีประสิทธิภาพมากนัก ในการทำนายโครงสร้างทุติยภูมิของ RNA รูปแบบต่างๆ ของอัลกอริทึม Cocke–Younger–Kasami (CYK)ให้ทางเลือกที่มีประสิทธิภาพมากกว่าสำหรับการแยกวิเคราะห์ไวยากรณ์มากกว่าออโตมาตาแบบพุชดาวน์[ 1 ] อีกตัวอย่างหนึ่งของตัวแยกวิเคราะห์ PCFG คือ Stanford Statistical Parser ซึ่งได้รับการฝึกฝนโดยใช้Treebank [ 2 ]

คำจำกัดความอย่างเป็นทางการ

เช่นเดียวกับไวยากรณ์ แบบบริบทอิสระ (CFG)ไวยากรณ์แบบบริบทอิสระเชิงความน่าจะเป็นG สามารถกำหนดได้ด้วยชุดห้าองค์ประกอบ:

จี=(เอ็ม,ที,อาร์,เอส,พี){\displaystyle G=(M,T,R,S,P)}

ที่ไหน

  • M คือเซตของสัญลักษณ์ที่ไม่ใช่เทอร์มินัล
  • T คือเซตของสัญลักษณ์เทอร์มินัล
  • R คือเซตของกฎการผลิต
  • S คือสัญลักษณ์เริ่มต้น
  • P คือเซตของความน่าจะเป็นของกฎการผลิต

ความสัมพันธ์กับแบบจำลองมาร์คอฟที่ซ่อนอยู่

แบบจำลอง PCFG ขยายไวยากรณ์แบบไร้บริบทในลักษณะเดียวกับที่แบบจำลองมาร์คอฟแบบซ่อนเร้นขยายไวยากรณ์แบบปกติ

อัลกอริทึม Inside -Outsideเป็นอัลกอริทึมที่คล้ายคลึงกับอัลกอริทึม Forward-Backwardโดยจะคำนวณความน่าจะเป็นรวมของการสร้างทั้งหมดที่สอดคล้องกับลำดับที่กำหนด โดยอิงจาก PCFG บางอย่าง ซึ่งเทียบเท่ากับความน่าจะเป็นที่ PCFG จะสร้างลำดับนั้นขึ้นมา และโดยสัญชาตญาณแล้วเป็นตัววัดว่าลำดับนั้นสอดคล้องกับไวยากรณ์ที่กำหนดมากน้อยเพียงใด อัลกอริทึม Inside-Outside ถูกนำมาใช้ในการกำหนดพารามิเตอร์ ของแบบจำลอง เพื่อประมาณความถี่เบื้องต้นที่สังเกตได้จากลำดับการฝึกอบรมในกรณีของ RNA

รูปแบบ การเขียนโปรแกรมเชิงพลวัตของอัลกอริธึม CYKค้นหาการแยกวิเคราะห์แบบ Viterbiของลำดับ RNA สำหรับแบบจำลอง PCFG การแยกวิเคราะห์นี้เป็นการอนุมานลำดับที่น่าจะเป็นไปได้มากที่สุดโดย PCFG ที่กำหนดให้

โครงสร้างไวยากรณ์

ไวยากรณ์แบบไร้บริบทแสดงเป็นชุดของกฎที่ได้รับแรงบันดาลใจจากความพยายามในการจำลองภาษาธรรมชาติ[ 3 ] [ 4 ] [ 5 ]กฎเหล่านี้เป็นแบบสัมบูรณ์และมีการแสดงไวยากรณ์แบบทั่วไปที่เรียกว่ารูปแบบ Backus–Naurกฎการผลิตประกอบด้วยเทอร์มินัล{เอ,ข}{\displaystyle \left\{a,b\right\}}และสัญลักษณ์ Sที่ไม่ใช่เทอร์มินัลและช่องว่างϵ{\displaystyle \epsilon }อาจใช้เป็นจุดสิ้นสุดได้เช่นกัน ในกฎการผลิตของ CFG และ PCFG ด้านซ้ายจะมีสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเพียงตัวเดียว ในขณะที่ด้านขวาสามารถเป็นสตริงของสัญลักษณ์เทอร์มินัลหรือสัญลักษณ์ที่ไม่ใช่เทอร์มินัลใดก็ได้ ใน PCFG จะไม่ใช้ค่าว่าง[ 1 ]ตัวอย่างไวยากรณ์:

เอส→เอเอส,เอส→ขเอส,เอส→ϵ{\displaystyle S\to aS,S\to bS,S\to \epsilon }

ไวยากรณ์นี้สามารถย่อให้สั้นลงได้โดยใช้เครื่องหมาย '|' ('หรือ') ดังนี้:

เอส→เอเอส|ขเอส|ϵ{\displaystyle S\to aS|bS|\epsilon }

เทอร์มินัลในไวยากรณ์คือคำ และตามกฎไวยากรณ์ สัญลักษณ์ที่ไม่ใช่เทอร์มินัลจะถูกแปลงเป็นสตริงของเทอร์มินัลและ/หรือสัญลักษณ์ที่ไม่ใช่เทอร์มินัล ไวยากรณ์ข้างต้นอ่านได้ว่า "เริ่มต้นจากสัญลักษณ์ที่ไม่ใช่เทอร์มินัลSการปล่อยสัญญาณสามารถสร้างได้ทั้งaหรือbหรือϵ{\displaystyle \epsilon }"ที่มาของมันคือ:

เอส⇒เอเอส⇒เอขเอส⇒เอขขเอส⇒เอขข{\displaystyle S\Rightarrow aS\Rightarrow aS\Rightarrow abbS\Rightarrow abb}

ไวยากรณ์ที่ไม่ชัดเจนอาจส่งผลให้การวิเคราะห์ไวยากรณ์ไม่ชัดเจนหากนำไปใช้กับคำที่มีการสะกดเหมือนกันแต่ความหมายต่างกัน เนื่องจากลำดับคำเดียวกันสามารถตีความได้มากกว่าหนึ่งแบบ ประโยคเล่นคำเช่น พาดหัวข่าวในหนังสือพิมพ์ "Iraqi Head Seeks Arms" เป็นตัวอย่างของการวิเคราะห์ไวยากรณ์ที่ไม่ชัดเจน

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

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

การกำหนดความน่าจะเป็นให้กับกฎการผลิตทำให้เกิด PCFG ความน่าจะเป็นเหล่านี้ได้รับข้อมูลจากการสังเกตการกระจายบนชุดฝึกอบรมที่มีองค์ประกอบคล้ายกับภาษาที่จะจำลอง ในตัวอย่างส่วนใหญ่ของภาษากว้าง ไวยากรณ์เชิงความน่าจะเป็นที่ประมาณความน่าจะเป็นจากข้อมูลมักจะมีประสิทธิภาพดีกว่าไวยากรณ์ที่สร้างขึ้นด้วยมือ CFG เมื่อเปรียบเทียบกับ PCFG ไม่สามารถนำไปใช้กับการทำนายโครงสร้าง RNA ได้ เนื่องจากถึงแม้ว่าจะรวมความสัมพันธ์ระหว่างลำดับและโครงสร้างไว้ แต่ก็ขาดเมตริกการให้คะแนนที่เปิดเผยศักยภาพเชิงโครงสร้างของลำดับ[ 6 ]

ไวยากรณ์แบบไร้บริบทที่มีน้ำหนัก

ไวยากรณ์แบบไร้บริบทที่มีน้ำหนัก ( WCFG ) เป็นหมวดหมู่ทั่วไปของไวยากรณ์แบบไร้บริบทโดยที่กฎการผลิตแต่ละข้อจะมีน้ำหนักตัวเลขที่เกี่ยวข้อง น้ำหนักของต้นไม้การวิเคราะห์ เฉพาะ ใน WCFG คือผลคูณ[ 7 ] (หรือผลรวม[ 8 ] ) ของน้ำหนักกฎทั้งหมดในต้นไม้ น้ำหนักกฎแต่ละข้อจะถูกรวมไว้บ่อยเท่ากับจำนวนครั้งที่ใช้กฎนั้นในต้นไม้ กรณีพิเศษของ WCFG คือ PCFG ซึ่งน้ำหนักคือ ความ น่าจะเป็น ( ลอการิทึมของ[ 9 ] [ 10 ] )

สามารถใช้ เวอร์ชันที่ขยายของอัลกอริธึม CYKเพื่อค้นหาอนุพันธ์ที่ "เบาที่สุด" (น้ำหนักน้อยที่สุด) ของสตริงที่กำหนดให้โดยใช้ WCFG บางอย่างได้

เมื่อน้ำหนักของต้นไม้เป็นผลคูณของน้ำหนักกฎ WCFG และ PCFG สามารถแสดงชุดการแจกแจงความน่าจะ เป็นเดียวกัน ได้[ 7 ]

แอปพลิเคชัน

การทำนายโครงสร้าง RNA

ตั้งแต่ทศวรรษ 1990 เป็นต้นมา PCFG ได้ถูกนำมาใช้เพื่อสร้างแบบจำลองโครงสร้างRNA [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]

การลดพลังงานให้เหลือน้อยที่สุด[ 16 ] [ 17 ]และ PCFG ให้วิธีการทำนายโครงสร้างทุติยภูมิของ RNA ที่มีประสิทธิภาพเทียบเท่ากัน[ 11 ] [ 12 ] [ 1 ]อย่างไรก็ตาม การทำนายโครงสร้างโดย PCFG จะถูกให้คะแนนตามความน่าจะเป็นมากกว่าการคำนวณพลังงานอิสระขั้นต่ำ พารามิเตอร์ของแบบจำลอง PCFG ได้มาจากความถี่ของคุณลักษณะต่างๆ ที่สังเกตได้ในฐานข้อมูลโครงสร้าง RNA โดยตรง[ 6 ]มากกว่าการกำหนดโดยการทดลองเช่นเดียวกับวิธีการลดพลังงานให้เหลือน้อย ที่สุด [ 18 ] [ 19 ]

โครงสร้างประเภทต่างๆ ที่สามารถจำลองได้ด้วย PCFG ได้แก่ ปฏิสัมพันธ์ระยะไกล โครงสร้างแบบคู่ และโครงสร้างแบบซ้อนกันอื่นๆ อย่างไรก็ตาม ไม่สามารถจำลอง pseudoknot ได้[ 11 ] [ 12 ] [ 1 ] PCFG ขยาย CFG โดยการกำหนดความน่าจะเป็นให้กับกฎการผลิตแต่ละข้อ ต้นไม้วิเคราะห์ที่มีความน่าจะเป็นสูงสุดจากไวยากรณ์บ่งบอกถึงโครงสร้างที่มีความน่าจะเป็นสูงสุด เนื่องจาก RNA รักษาโครงสร้างไว้ตลอดลำดับหลัก การทำนายโครงสร้าง RNA จึงสามารถชี้นำได้โดยการรวมข้อมูลวิวัฒนาการจากการวิเคราะห์ลำดับเปรียบเทียบกับความรู้ทางชีวฟิสิกส์เกี่ยวกับความเป็นไปได้ของโครงสร้างโดยอิงจากความน่าจะเป็นดังกล่าว นอกจากนี้ ผลการค้นหาโครงสร้างที่คล้ายคลึงกันโดยใช้กฎ PCFG จะได้รับการให้คะแนนตามความน่าจะเป็นของการอนุมาน PCFG ดังนั้น การสร้างไวยากรณ์เพื่อจำลองพฤติกรรมของคู่เบสและบริเวณสายเดี่ยวจึงเริ่มต้นด้วยการสำรวจคุณลักษณะของการจัดเรียงลำดับหลายลำดับ เชิงโครงสร้าง ของ RNA ที่เกี่ยวข้อง[ 1 ]

เอส→เอเอสเอ|ขเอสข|เอเอ|ขข{\displaystyle S\to aSa|bSb|aa|bb}

ไวยากรณ์ข้างต้นสร้างสตริงในลักษณะจากภายนอกสู่ภายใน กล่าวคือ คู่เบสที่อยู่ปลายสุดของเทอร์มินัลจะถูกสร้างขึ้นก่อน ดังนั้นสตริงเช่นนี้เอเอขเอเอขเอเอ{\displaystyle aabaabaa}ได้มาจากการสร้างตัวอักษร'a ' ที่อยู่ไกลที่สุดทั้งสองด้านก่อน จากนั้นจึงค่อยเคลื่อนเข้ามาด้านใน:

เอส⇒เอเอสเอ⇒เอเอเอสเอเอ⇒เอเอขเอสขเอเอ⇒เอเอขเอเอขเอเอ{\displaystyle S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabaabaa}

ความสามารถในการขยายของแบบจำลอง PCFG ช่วยให้สามารถจำกัดการทำนายโครงสร้างโดยการรวมความคาดหวังเกี่ยวกับคุณลักษณะต่างๆ ของ RNA ความคาดหวังดังกล่าวอาจสะท้อนถึงแนวโน้มในการสมมติโครงสร้างบางอย่างโดย RNA เป็นต้น[ 6 ] อย่างไรก็ตาม การรวมข้อมูลมากเกินไปอาจเพิ่มพื้นที่และความซับซ้อนของหน่วยความจำของ PCFG และเป็นที่พึงปรารถนาว่าแบบจำลองที่ใช้ PCFG ควรเรียบง่ายที่สุดเท่าที่จะเป็นไปได้[ 6 ] [ 20 ]

สตริง xทุกสตริงที่เป็นไปได้ที่ไวยากรณ์สร้างขึ้น จะถูกกำหนดค่าน้ำหนักความน่าจะเป็นพี(x|θ){\displaystyle P(x|\theta )}โดยพิจารณาจากแบบจำลอง PCFGθ{\displaystyle \theta }ดังนั้น ผลรวมของความน่าจะเป็นทั้งหมดสำหรับกฎไวยากรณ์ที่เป็นไปได้ทั้งหมดจึงเท่ากับ ∑xพี(x|θ)=1{\displaystyle \sum _{\text{x}}P(x|\theta )=1}คะแนนสำหรับสารตกค้างที่จับคู่และไม่จับคู่แต่ละรายการจะอธิบายความเป็นไปได้ของการก่อตัวของโครงสร้างทุติยภูมิ กฎการผลิตยังอนุญาตให้ให้คะแนนความยาวของลูป เช่นเดียวกับลำดับของ การเรียง ซ้อนของคู่เบสดังนั้นจึงเป็นไปได้ที่จะสำรวจช่วงของรุ่นที่เป็นไปได้ทั้งหมด รวมถึงโครงสร้างที่ไม่เหมาะสมจากไวยากรณ์ และยอมรับหรือปฏิเสธโครงสร้างตามเกณฑ์คะแนน[ 1 ] [ 6 ]

การนำไปใช้

การนำโครงสร้างทุติยภูมิของ RNA ไปใช้โดยอาศัยแนวทาง PCFG สามารถนำไปใช้ได้ในด้านต่างๆ ดังนี้:

  • การค้นหาโครงสร้างฉันทามติโดยการเพิ่มประสิทธิภาพความน่าจะเป็นร่วมของโครงสร้างเหนือ MSA [ 20 ] [ 21 ]
  • การสร้างแบบจำลองความแปรผันร่วมของคู่เบสเพื่อตรวจจับความเหมือนกันในการค้นหาฐานข้อมูล[ 11 ]
  • การพับและการจัดเรียงพร้อมกันแบบคู่[ 22 ] [ 23 ]

มีการนำแนวทางเหล่านี้ไปใช้ที่แตกต่างกัน ตัวอย่างเช่น Pfold ใช้ในการทำนายโครงสร้างทุติยภูมิจากกลุ่มลำดับ RNA ที่เกี่ยวข้อง[ 20 ]โมเดลความแปรปรวนร่วมใช้ในการค้นหาฐานข้อมูลสำหรับลำดับที่เหมือนกันและการระบุและการจำแนกประเภท RNA [ 11 ] [ 24 ] RNApromo, CMFinder และ TEISER ใช้ในการค้นหารูปแบบโครงสร้างที่เสถียรใน RNA [ 25 ] [ 26 ] [ 27 ]

ข้อควรพิจารณาในการออกแบบ

การออกแบบ PCFG ส่งผลต่อความแม่นยำในการทำนายโครงสร้างทุติยภูมิ แบบจำลองความน่าจะเป็นการทำนายโครงสร้างที่มีประโยชน์ใดๆ ที่อิงตาม PCFG จะต้องรักษาความเรียบง่ายโดยไม่ลดทอนความแม่นยำในการทำนายมากนัก แบบจำลองที่ซับซ้อนเกินไปซึ่งมีประสิทธิภาพดีเยี่ยมในลำดับเดียวอาจไม่สามารถปรับขนาดได้[ 1 ]แบบจำลองที่อิงตามไวยากรณ์ควรจะสามารถ:

  • ค้นหาการจัดเรียงที่เหมาะสมที่สุดระหว่างลำดับและ PCFG
  • ประเมินความน่าจะเป็นของโครงสร้างสำหรับลำดับและลำดับย่อย
  • กำหนดพารามิเตอร์ของโมเดลโดยการฝึกฝนด้วยลำดับ/โครงสร้างต่างๆ
  • ค้นหาแผนผังโครงสร้างไวยากรณ์ที่เหมาะสมที่สุด (อัลกอริธึม CYK)
  • ตรวจสอบไวยากรณ์ที่กำกวม (อัลกอริธึม Conditional Inside)

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

สามารถแยกความกำกวมออกเป็นสองประเภท ได้แก่ ความกำกวมของแผนผังการวิเคราะห์ และความกำกวมเชิงโครงสร้าง ความกำกวมเชิงโครงสร้างไม่มีผลต่อวิธีการทางเทอร์โมไดนามิก เนื่องจากการเลือกโครงสร้างที่เหมาะสมที่สุดจะขึ้นอยู่กับคะแนนพลังงานอิสระที่ต่ำที่สุดเสมอ[ 6 ]ความกำกวมของแผนผังการวิเคราะห์เกี่ยวข้องกับการมีแผนผังการวิเคราะห์หลายแผนผังต่อลำดับ ความกำกวมดังกล่าวสามารถเปิดเผยโครงสร้างการจับคู่เบสที่เป็นไปได้ทั้งหมดสำหรับลำดับโดยการสร้างแผนผังการวิเคราะห์ที่เป็นไปได้ทั้งหมด จากนั้นจึงค้นหาแผนผังที่เหมาะสมที่สุด[ 28 ] [ 29 ] [ 30 ]ในกรณีของความกำกวมเชิงโครงสร้าง แผนผังการวิเคราะห์หลายแผนผังอธิบายโครงสร้างทุติยภูมิเดียวกัน ซึ่งทำให้การตัดสินใจของอัลกอริทึม CYK ในการค้นหาโครงสร้างที่เหมาะสมที่สุดไม่ชัดเจน เนื่องจากความสอดคล้องระหว่างแผนผังการวิเคราะห์และโครงสร้างไม่เป็นเอกลักษณ์[ 31 ]สามารถตรวจสอบความกำกวมของไวยากรณ์ได้โดยใช้อัลกอริทึมเงื่อนไขภายใน[ 1 ] [ 6 ]

การสร้างแบบจำลอง PCFG

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

การเริ่มต้นที่ไม่ใช่เทอร์มินัลเอส{\displaystyle \mathbf {\mathit {S}} }ก่อให้เกิดลูป ส่วนที่เหลือของไวยากรณ์ดำเนินไปโดยใช้พารามิเตอร์แอล{\displaystyle \mathbf {\mathit {L}} }ที่ตัดสินว่าลูปนั้นเป็นจุดเริ่มต้นของลำต้นหรือบริเวณสายเดี่ยวและพารามิเตอร์sเอฟ{\displaystyle \mathbf {\mathit {F}} }ซึ่งสร้างเบสคู่

รูปแบบทางคณิตศาสตร์ของ PCFG แบบง่ายนี้มีลักษณะดังนี้:

เอส→แอลเอส|แอล{\displaystyle {\mathit {S\to LS|L}}}
แอล→ส|งเอฟง{\displaystyle {\mathit {L\to s|dFd}}}
เอฟ→งเอฟง|แอลเอส{\displaystyle {\mathit {F\to dFd|LS}}}

การประยุกต์ใช้ PCFG ในการทำนายโครงสร้างเป็นกระบวนการหลายขั้นตอน นอกจากนี้ PCFG เองยังสามารถรวมเข้ากับแบบจำลองความน่าจะเป็นที่พิจารณาประวัติวิวัฒนาการของ RNA หรือค้นหาลำดับที่คล้ายคลึงกันในฐานข้อมูล ในบริบทของประวัติวิวัฒนาการ การรวมการแจกแจงก่อนหน้าของโครงสร้าง RNA ของการจัดเรียงโครงสร้างในกฎการสร้างของ PCFG ช่วยให้มีความแม่นยำในการทำนายที่ดี[ 21 ]

สรุปขั้นตอนทั่วไปสำหรับการใช้งาน PCFG ในสถานการณ์ต่างๆ:

  • สร้างกฎการผลิตสำหรับลำดับต่างๆ
  • ตรวจสอบความกำกวม
  • สร้างแผนผังการวิเคราะห์โครงสร้างที่เป็นไปได้โดยใช้ไวยากรณ์แบบเรียกซ้ำ
  • จัดอันดับและให้คะแนนต้นไม้การวิเคราะห์สำหรับลำดับที่น่าจะเป็นไปได้มากที่สุด[ 1 ]

อัลกอริทึม

มีอัลกอริธึมหลายตัวที่เกี่ยวข้องกับแง่มุมของแบบจำลองความน่าจะเป็นตาม PCFG ในการทำนายโครงสร้าง RNA ตัวอย่างเช่น อัลกอริธึม inside-outside และอัลกอริธึม CYK อัลกอริธึม inside-outside เป็นอัลกอริธึมการให้คะแนนการเขียนโปรแกรมเชิงไดนามิกแบบเรียกซ้ำที่สามารถปฏิบัติตาม แบบแผน ความคาดหวัง-การทำให้สูงสุดได้ มันคำนวณความน่าจะเป็นทั้งหมดของอนุพันธ์ทั้งหมดที่สอดคล้องกับลำดับที่กำหนดโดยอิงจาก PCFG บางส่วน ส่วน inside จะให้คะแนนต้นไม้ย่อยจากต้นไม้การวิเคราะห์และดังนั้นความน่าจะเป็นของลำดับย่อยที่กำหนดโดย PCFG ส่วน outside จะให้คะแนนความน่าจะเป็นของต้นไม้การวิเคราะห์ที่สมบูรณ์สำหรับลำดับทั้งหมด[ 32 ] [ 33 ] CYK ปรับเปลี่ยนการให้คะแนน inside-outside โปรดทราบว่าคำว่า 'อัลกอริธึม CYK' อธิบายถึงตัวแปร CYK ของอัลกอริธึม inside ที่ค้นหาต้นไม้การวิเคราะห์ที่เหมาะสมที่สุดสำหรับลำดับโดยใช้ PCFG มันขยายอัลกอริธึม CYK จริง ที่ใช้ใน CFG ที่ไม่ใช่ความน่าจะเป็น[ 1 ]

อัลกอริทึมภายในคำนวณα(ฉัน,เจ,วี){\displaystyle \alpha (i,j,v)}ความน่าจะเป็นสำหรับทั้งหมดฉัน,เจ,วี{\displaystyle i,j,v} ของซับทรีการวิเคราะห์ที่รากอยู่ที่ววี{\displaystyle W_{v}}สำหรับลำดับย่อยxฉัน,...,xเจ{\displaystyle x_{i},...,x_{j}}อัลกอริทึมภายนอกคำนวณเบต้า(ฉัน,เจ,วี){\displaystyle \beta (i,j,v)}ความน่าจะเป็นของแผนผังการวิเคราะห์ที่สมบูรณ์สำหรับลำดับxจากราก โดยไม่รวมการคำนวณของxฉัน,...,xเจ{\displaystyle x_{i},...,x_{j}}ตัวแปรαและβช่วยปรับปรุงการประมาณค่าพารามิเตอร์ความน่าจะเป็นของ PCFG สามารถประมาณค่าอัลกอริธึม PCFG ใหม่ได้โดยการหาจำนวนครั้งที่คาดว่าจะใช้สถานะหนึ่งๆ ในการอนุมาน โดยการรวมผลคูณทั้งหมดของαและβหารด้วยความน่าจะเป็นสำหรับลำดับxที่กำหนดโดยแบบจำลองพี(x|θ){\displaystyle P(x|\theta )}นอกจากนี้ยังสามารถหาจำนวนครั้งที่คาดว่าจะใช้กฎการผลิตได้โดยใช้การคาดการณ์-การเพิ่มค่าสูงสุดที่ใช้ค่าของαและ β [ 32 ] [ 33 ] อัลกอริทึม CYK คำนวณγ(ฉัน,เจ,วี){\displaystyle \gamma (i,j,v)}เพื่อค้นหาแผนผังการวิเคราะห์ที่มีความเป็นไปได้มากที่สุดπ^{\displaystyle {\hat {\pi }}}และผลผลิตบันทึก⁡พี(x,π^|θ){\displaystyle \log P(x,{\hat {\pi }}|\theta )}[ 1 ]​

ความซับซ้อนของหน่วยความจำและเวลาสำหรับอัลกอริธึม PCFG ทั่วไปในการทำนายโครงสร้าง RNA คือโอ(แอล2เอ็ม){\displaystyle O(L^{2}M)}และโอ(แอล3เอ็ม3){\displaystyle O(L^{3}M^{3})}ตามลำดับ การจำกัด PCFG อาจเปลี่ยนแปลงข้อกำหนดนี้ได้ เช่นเดียวกับวิธีการค้นหาในฐานข้อมูล

แบบจำลองความแปรปรวนร่วม (CMs) เป็น PCFG ประเภทพิเศษที่มีการประยุกต์ใช้ในการค้นหาฐานข้อมูลสำหรับโฮโมล็อก คำอธิบายประกอบ และการจำแนกประเภท RNA ด้วย CMs ทำให้สามารถสร้างโปรไฟล์ RNA ที่ใช้ PCFG ได้ โดยที่ RNA ที่เกี่ยวข้องสามารถแสดงได้ด้วยโครงสร้างทุติยภูมิที่เป็นเอกฉันท์[ 11 ] [ 12 ]แพ็คเกจวิเคราะห์ RNA Infernal ใช้โปรไฟล์ดังกล่าวในการอนุมานการจัดเรียง RNA [ 34 ]ฐานข้อมูล Rfam ยังใช้ CMs ในการจำแนก RNA ออกเป็นตระกูลตามโครงสร้างและข้อมูลลำดับ[ 24 ]

CM ถูกออกแบบจากโครงสร้าง RNA ที่เป็นฉันทามติ CM อนุญาตให้มีการแทรกหรือลบที่มีความยาวไม่จำกัดในการจัดเรียงลำดับ เทอร์มินัลประกอบเป็นสถานะใน CM และความน่าจะเป็นของการเปลี่ยนผ่านระหว่างสถานะจะเป็น 1 หากไม่มีการพิจารณาการแทรกหรือลบ[ 1 ]ไวยากรณ์ใน CM มีดังต่อไปนี้:

พี→เอวข{\displaystyle P\to aWb}
ความน่าจะเป็นของการปฏิสัมพันธ์แบบคู่ระหว่างคู่ที่เป็นไปได้ 16 คู่
แอล→เอว{\displaystyle L\to aW}
ความน่าจะเป็นของการสร้างเบสเดี่ยวที่เป็นไปได้ 4 แบบทางด้านซ้าย
อาร์→วเอ{\displaystyle R\to Wa}
ความน่าจะเป็นของการสร้างเบสเดี่ยวที่เป็นไปได้ 4 แบบทางด้านขวา
บี→เอสเอส{\displaystyle B\to SS}
การแตกแขนงด้วยความน่าจะเป็น 1
เอส→ว{\displaystyle S\to W}
เริ่มต้นด้วยค่าความน่าจะเป็น 1
อี→ϵ{\displaystyle E\ถึง \epsilon }
จบด้วยความน่าจะเป็น 1

แบบจำลองมีสถานะที่เป็นไปได้ 6 สถานะ และไวยากรณ์ของแต่ละสถานะประกอบด้วยความน่าจะเป็นของโครงสร้างรองประเภทต่างๆ ของไม่ใช่เทอร์มินัล สถานะต่างๆ เชื่อมต่อกันด้วยการเปลี่ยนสถานะ ในอุดมคติแล้ว สถานะโหนดปัจจุบันจะเชื่อมต่อกับสถานะแทรกทั้งหมด และสถานะโหนดถัดไปจะเชื่อมต่อกับสถานะที่ไม่ใช่แทรก เพื่อให้สามารถแทรกฐานแทรกได้มากกว่าหนึ่งฐาน สถานะแทรกจะเชื่อมต่อกับตัวเอง[ 1 ]

ในการให้คะแนนโมเดล CM จะใช้อัลกอริธึมภายในและภายนอก โมเดล CM ใช้การใช้งาน CYK ที่แตกต่างออกไปเล็กน้อย คะแนนการปล่อย Log-odds สำหรับแผนผังการวิเคราะห์ที่ดีที่สุด -บันทึก⁡อี^{\displaystyle \log {\หมวก {e}}}- คำนวณจากสถานะการปล่อยพี, แอล, อาร์{\displaystyle P,~L,~R}เนื่องจากคะแนนเหล่านี้เป็นฟังก์ชันของความยาวลำดับ ดังนั้นจึงจำเป็นต้องใช้มาตรวัดที่มีความแม่นยำกว่าเพื่อหาคะแนนความน่าจะเป็นของแผนผังการวิเคราะห์ไวยากรณ์ที่ดีที่สุดบันทึก⁡พี(x,π^|θ){\displaystyle \log {\text{P}}(x,{\hat {\pi }}|\theta )}- บรรลุผลได้โดยการจำกัดความยาวสูงสุดของลำดับที่จะจัดเรียงและคำนวณค่าลอการิทึมของอัตราส่วนความน่าจะเป็นเทียบกับค่าว่าง เวลาในการคำนวณของขั้นตอนนี้เป็นเชิงเส้นตามขนาดของฐานข้อมูล และอัลกอริทึมมีความซับซ้อนของหน่วยความจำเท่ากับโอ(เอ็มเอดี+เอ็มขดี2){\displaystyle O(M_{a}D+M_{b}D^{2})}[ 1 ]​

ตัวอย่าง: การใช้ข้อมูลวิวัฒนาการเพื่อเป็นแนวทางในการทำนายโครงสร้าง

อัลกอริทึม KH-99 โดย Knudsen และ Hein เป็นพื้นฐานของแนวทาง Pfold ในการทำนายโครงสร้างทุติยภูมิของ RNA [ 20 ]ในแนวทางนี้ การกำหนดพารามิเตอร์ต้องใช้ข้อมูลประวัติวิวัฒนาการที่ได้มาจากต้นไม้การจัดเรียง นอกเหนือจากความน่าจะเป็นของคอลัมน์และการกลายพันธุ์ ความน่าจะเป็นของไวยากรณ์จะถูกสังเกตจากชุดข้อมูลการฝึกอบรม

ประมาณค่าความน่าจะเป็นของคอลัมน์สำหรับฐานที่จับคู่และไม่จับคู่

ในการจัดเรียงโครงสร้าง ความน่าจะเป็นของคอลัมน์เบสเดี่ยวและคอลัมน์เบสคู่จะเป็นอิสระจากคอลัมน์อื่นๆ โดยการนับเบสในตำแหน่งเบสเดี่ยวและตำแหน่งเบสคู่ จะได้ความถี่ของเบสในลูปและลำต้น สำหรับคู่เบสXและYการเกิดขึ้นของXวาย{\displaystyle XY}นับเป็นเหตุการณ์หนึ่งด้วยเช่นกันวายX{\displaystyle YX}คู่เบสที่เหมือนกัน เช่นXX{\displaystyle XX}นับสองครั้ง

คำนวณอัตราการกลายพันธุ์สำหรับเบสที่จับคู่กันและเบสที่ไม่จับคู่กัน

โดยการจับคู่ลำดับในทุกวิธีที่เป็นไปได้ จะสามารถประมาณอัตราการกลายพันธุ์โดยรวมได้ เพื่อให้สามารถระบุการกลายพันธุ์ที่น่าจะเป็นไปได้ ควรใช้เกณฑ์ความเหมือนของลำดับเพื่อให้การเปรียบเทียบเกิดขึ้นระหว่างลำดับที่คล้ายคลึงกัน วิธีนี้ใช้เกณฑ์ความเหมือน 85% ระหว่างลำดับที่จับคู่กัน ขั้นแรก จะนับความแตกต่างของตำแหน่งเบสเดี่ยว (ยกเว้นคอลัมน์ที่มีช่องว่าง) ระหว่างคู่ลำดับ โดยที่หากตำแหน่งเดียวกันในสองลำดับมีเบสX, Y ที่แตกต่างกัน จำนวนความแตกต่างจะเพิ่มขึ้นสำหรับแต่ละลำดับ

ในขณะที่X≠วาย{\displaystyle X\neq Y}ซีXY+1{\displaystyle C_{\text{XY}}+1}คู่ลำดับแรกซีวายเอ็กซ์+1{\displaystyle C_{\text{YX}}+1}คู่ลำดับที่สอง
คำนวณอัตราการกลายพันธุ์ให้ รXY={\displaystyle r_{\text{XY}}=}การกลายพันธุ์ของเบส X เป็นเบส Y=เค ซีXYพีxพีส{\displaystyle ={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}}อนุญาต รXX={\displaystyle r_{\text{XX}}=}ค่าลบของอัตราการกลายพันธุ์ของโครโมโซม X ไปเป็นเบสอื่น=−∑รXY{\displaystyle =-\sum r_{\text{XY}}}พีส={\displaystyle P_{s}=}ความน่าจะเป็นที่เบสจะไม่จับคู่กัน

สำหรับเบสที่ไม่มีคู่ จะใช้เมทริกซ์อัตราการกลายพันธุ์ 4 x 4 ที่ตรงตามเงื่อนไขที่ว่าการไหลของการกลายพันธุ์จาก X ไปยัง Y สามารถย้อนกลับได้: [ 35 ]

พีXรXวาย=พีวายรวายX{\displaystyle PX^{r}XY=PY^{r}YX}

สำหรับคู่เบส จะมีการสร้างเมทริกซ์การกระจายอัตรา 16 x 16 ในทำนองเดียวกัน[ 36 ] [ 37 ] PCFG ใช้ในการทำนาย การกระจาย ความน่าจะเป็นก่อนหน้าของโครงสร้าง ในขณะที่ความน่าจะเป็นภายหลังจะถูกประมาณโดยอัลกอริทึมภายใน-ภายนอก และโครงสร้างที่น่าจะเป็นไปได้มากที่สุดจะถูกค้นพบโดยอัลกอริทึม CYK [ 20 ]

ประเมินความน่าจะเป็นของการจัดเรียง

หลังจากคำนวณความน่าจะเป็นเบื้องต้นของคอลัมน์แล้ว จะประมาณความน่าจะเป็นของการจัดเรียงโดยการรวมค่าจากโครงสร้างทุติยภูมิที่เป็นไปได้ทั้งหมด คอลัมน์C ใดๆ ในโครงสร้างทุติยภูมิσ{\displaystyle \sigma }สำหรับลำดับDที่มีความยาวlโดยที่ดี=(ซี1, ซี2,...ซีล){\displaystyle D=(C_{1},~C_{2},...C_{l})}สามารถให้คะแนนได้โดยอ้างอิงจากแผนผังการจัดเรียงTและแบบจำลองการกลายพันธุ์Mการแจกแจงความน่าจะเป็นล่วงหน้าที่กำหนดโดย PCFG คือพี(σ|เอ็ม){\displaystyle P(\sigma |M)}ต้นไม้วิวัฒนาการ T สามารถคำนวณได้จากแบบจำลองโดย การประมาณค่าความน่าจะ เป็นสูงสุดโปรดทราบว่าช่องว่างถือเป็นฐานที่ไม่ทราบค่า และผลรวมสามารถทำได้ผ่าน การ เขียนโปรแกรมแบบไดนามิก[ 38 ]

พี(ดี|ที,เอ็ม){\displaystyle P(D|T,M)}
=∑พี(ดี,σ|ที,เอ็ม){\displaystyle =\sum P(D,\sigma |T,M)}
=∑พี(ดี|σ,ที,เอ็ม)พี(σ|ที,เอ็ม){\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |T,M)}
=∑พี(ดี|σ,ที,เอ็ม)พี(σ|เอ็ม){\displaystyle =\sum P(D|\sigma ,T,M)P(\sigma |M)}
กำหนดความน่าจะเป็นในการผลิตให้กับแต่ละกฎในไวยากรณ์

โครงสร้างแต่ละโครงสร้างในไวยากรณ์จะได้รับความน่าจะเป็นในการผลิตที่คิดค้นขึ้นจากโครงสร้างของชุดข้อมูลการฝึกอบรม ความน่าจะเป็นล่วงหน้าเหล่านี้จะให้น้ำหนักกับความแม่นยำในการคาดการณ์[ 21 ] [ 32 ] [ 33 ]จำนวนครั้งที่ใช้กฎแต่ละข้อขึ้นอยู่กับการสังเกตจากชุดข้อมูลการฝึกอบรมสำหรับคุณลักษณะไวยากรณ์เฉพาะนั้น ความน่าจะเป็นเหล่านี้จะถูกเขียนไว้ในวงเล็บในรูปแบบไวยากรณ์ และแต่ละกฎจะมีค่ารวม 100% [ 20 ]ตัวอย่างเช่น:

เอส→แอลเอส(80%)|แอล(20%){\displaystyle S\to LS(80\%)|L(20\%)}
แอล→ส(70%)|งเอฟง(30%){\displaystyle L\to s(70\%)|dFd(30\%)}
เอฟ→งเอฟง(60.4%)|แอลเอส(39.6%){\displaystyle F\to dFd(60.4\%)|LS(39.6\%)}
ทำนายความน่าจะเป็นของโครงสร้าง

เมื่อพิจารณาความถี่การจัดเรียงข้อมูลก่อนหน้าแล้ว โครงสร้างที่มีความเป็นไปได้มากที่สุดจากกลุ่มที่ทำนายโดยไวยากรณ์สามารถคำนวณได้โดยการเพิ่มค่าสูงสุดพี(σ|ดี,ที,เอ็ม){\displaystyle P(\sigma |D,T,M)}ผ่านอัลกอริธึม CYK โครงสร้างที่มีจำนวนการทำนายที่ถูกต้องสูงสุดจะถูกรายงานว่าเป็นโครงสร้างฉันทามติ[ 20 ]

σเอ็มเอพี=อาร์ก⁡สูงสุดσพี(ดี|σ,ทีเอ็มแอล,เอ็ม)พี(σ|เอ็ม){\displaystyle \sigma _{MAP}=\arg {\underset {\sigma }{\max }}P(D|\sigma ,T^{M}L,M)P(\sigma |M)}
การปรับปรุง Pfold บนอัลกอริทึม KH-99

แนวทางที่ใช้ PCFG นั้นเป็นที่ต้องการให้สามารถปรับขนาดได้และมีความเป็นทั่วไปเพียงพอ การลดความเร็วเพื่อความแม่นยำต้องน้อยที่สุดเท่าที่จะเป็นไปได้ Pfold แก้ไขข้อจำกัดของอัลกอริธึม KH-99 ในแง่ของความสามารถในการปรับขนาด ช่องว่าง ความเร็ว และความแม่นยำ[ 20 ]

  • ใน Pfold ช่องว่างจะถูกมองว่าไม่ทราบค่า ในแง่นี้ ความน่าจะเป็นของคอลัมน์ที่มีช่องว่างจึงเท่ากับความน่าจะเป็นของคอลัมน์ที่ไม่มีช่องว่าง
  • ใน Pfold ต้นไม้Tจะถูกคำนวณก่อนการทำนายโครงสร้างโดยใช้วิธีNeighbor Joiningไม่ใช่โดยวิธี Maximum Likelihood ผ่านไวยากรณ์ PCFG มีเพียงความยาวของกิ่งเท่านั้นที่จะถูกปรับให้เข้ากับค่าประมาณ Maximum Likelihood
  • ข้อสมมติฐานหนึ่งของ Pfold คือ ลำดับทั้งหมดมีโครงสร้างเหมือนกัน เกณฑ์ความเหมือนของลำดับและการอนุญาตให้มีความน่าจะเป็น 1% ที่นิวคลีโอไทด์ใดๆ จะเปลี่ยนเป็นนิวคลีโอไทด์อื่น จะช่วยจำกัดการลดลงของประสิทธิภาพเนื่องจากข้อผิดพลาดในการจัดเรียงลำดับ

การวิเคราะห์ลำดับโปรตีน

ในขณะที่ PCFG ได้พิสูจน์แล้วว่าเป็นเครื่องมือที่มีประสิทธิภาพในการทำนายโครงสร้างทุติยภูมิของ RNA แต่การใช้งานในด้านการวิเคราะห์ลำดับโปรตีนนั้นมีจำกัด อันที่จริง ขนาดของ ตัวอักษร กรดอะมิโนและความหลากหลายของปฏิสัมพันธ์ที่พบในโปรตีนทำให้การอนุมานไวยากรณ์มีความท้าทายมากขึ้น[ 39 ]ด้วยเหตุนี้ การประยุกต์ใช้ทฤษฎีภาษาเชิงรูปธรรม ส่วนใหญ่ ในการวิเคราะห์โปรตีนจึงถูกจำกัดไว้เฉพาะการสร้างไวยากรณ์ที่มีพลังการแสดงออกต่ำกว่าเพื่อจำลองรูปแบบการทำงานที่เรียบง่ายโดยอิงจากปฏิสัมพันธ์เฉพาะที่[ 40 ] [ 41 ]เนื่องจากโครงสร้างโปรตีนมักแสดงการพึ่งพาที่มีลำดับสูงกว่า รวมถึงความสัมพันธ์แบบซ้อนกันและแบบไขว้ จึงเกินขีดความสามารถของ CFG ใดๆ อย่างชัดเจน[ 39 ]อย่างไรก็ตาม การพัฒนา PCFG ช่วยให้สามารถแสดงการพึ่งพาเหล่านั้นบางส่วนและให้ความสามารถในการจำลองรูปแบบโปรตีนที่หลากหลายมากขึ้น

ดูเพิ่มเติม

  1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 R. Durbin; S. Eddy; A. Krogh; G. Mitchinson (1998). การวิเคราะห์ลำดับทางชีววิทยา: แบบจำลองความน่าจะเป็นของโปรตีนและกรดนิวคลีอิกสำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ISBN 978-0-521-62971-3.
  2. ↑ Klein, Daniel; Manning, Christopher (2003). "การวิเคราะห์ไวยากรณ์แบบไม่ใช้คำศัพท์ที่แม่นยำ" (PDF)รายงานการประชุมครั้งที่ 41 ของสมาคมภาษาศาสตร์เชิงคำนวณ : 423– 430.
  3. ↑ Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory . 2 (3): 113– 124. doi : 10.1109/TIT.1956.1056813 . S2CID 19519474 . 
  4. ↑ Chomsky, Noam (มิถุนายน 1959). "เกี่ยวกับคุณสมบัติเชิงรูปแบบบางประการของไวยากรณ์" . ข้อมูลและการควบคุม . 2 (2): 137– 167. doi : 10.1016/S0019-9958(59)90362-6 .
  5. ↑ Noam Chomsky, บรรณาธิการ (1957). โครงสร้างทางไวยากรณ์ . สำนักพิมพ์ Mouton & Co., เดนฮาก, เนเธอร์แลนด์.
  6. 1 2 3 4 5 6 7 Dowell R. & Eddy S. (2004). "การประเมินไวยากรณ์แบบบริบทอิสระเชิงสุ่มน้ำหนักเบาหลายแบบสำหรับการทำนายโครงสร้างทุติยภูมิของ RNA" BMC Bioinformatics 5 ( 71): 71. doi : 10.1186/1471-2105-5-71 . PMC 442121 . PMID 15180907 .  
  7. 1 2 Smith, Noah A.; Johnson, Mark (2007). "ไวยากรณ์แบบไร้บริบทที่มีน้ำหนักและแบบความน่าจะเป็นสามารถแสดงออกได้เท่าเทียมกัน" (PDF)ภาษาศาสตร์เชิงคำนวณ33 (4): 477. doi : 10.1162/coli.2007.33.4.477 . S2CID 1405777 . 
  8. ↑ Katsirelos, George; Narodytska, Nina; Walsh, Toby (2008). "ข้อจำกัด CFG แบบถ่วงน้ำหนัก"การบูรณาการเทคนิค AI และ OR ในการเขียนโปรแกรมข้อจำกัดสำหรับปัญหาการเพิ่มประสิทธิภาพเชิงรวม Lecture Notes in Computer Science. Vol. 5015. หน้า323–327 . CiteSeerX 10.1.1.150.1187 . doi : 10.1007/978-3-540-68155-7_31 . ISBN    978-3-540-68154-0. S2CID 9375313 . 
  9. ↑ จอห์นสัน, มาร์ค (2005). "แบบจำลองเชิงเส้นลอการิทึมหรือแบบจำลองกิบส์" (PDF )
  10. ↑ Chi, Zhiyi (มีนาคม 1999). "คุณสมบัติทางสถิติของไวยากรณ์แบบไร้บริบทเชิงความน่าจะเป็น" (PDF)ภาษาศาสตร์เชิงคำนวณ 25 ( 1): 131– 160. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 21 สิงหาคม 2010
  11. 1 2 3 4 5 6 Eddy SR & Durbin R. (1994). "การวิเคราะห์ลำดับ RNA โดยใช้แบบจำลองความแปรปรวนร่วม" . Nucleic Acids Research . 22 (11): 2079– 2088. doi : 10.1093/nar/22.11.2079 . PMC 308124 . PMID 8029015 .  
  12. 1 2 3 4 Sakakibara Y.; Brown M.; Hughey R.; Mian IS; และคณะ (1994). "ไวยากรณ์แบบไร้บริบทเชิงสุ่มสำหรับการสร้างแบบจำลอง tRNA" . Nucleic Acids Research . 22 (23): 5112– 5120. doi : 10.1093/nar/22.23.5112 . PMC 523785 . PMID 7800507 .   
  13. ↑ Grat, L. (1995). "การกำหนดโครงสร้างทุติยภูมิของ RNA โดยอัตโนมัติด้วยไวยากรณ์แบบไร้บริบทเชิงสุ่ม" (PDF)ในRawlings, C., Clark, D., Altman, R., Hunter, L., Lengauer, T และ Wodak, S. รายงานการประชุมนานาชาติครั้งที่ 3 ว่าด้วยระบบอัจฉริยะสำหรับชีววิทยาโมเลกุล, AAAI Press : 136– 144. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2015-12-04 . สืบค้นเมื่อ2017-08-03 .
  14. ↑ Lefebvre, F (1995). "อัลกอริทึมการแยกวิเคราะห์ที่ปรับให้เหมาะสมซึ่งเหมาะกับการพับ RNA" ใน Rawlings, C.; Clark, D.; Altman, R.; Hunter, L.; Lengauer, T.; Wodak, S. (บรรณาธิการ). รายงานการประชุมนานาชาติครั้งที่ 3 ว่าด้วยระบบอัจฉริยะสำหรับชีววิทยาโมเลกุล (PDF)สำนักพิมพ์ AAAI หน้า222–230 
  15. ↑ Lefebvre, F. (1996). "การรวมอัลกอริทึมการจัดเรียงและการพับหลายแบบโดยใช้ไวยากรณ์" ใน States, DJ; Agarwal, P.; Gaasterlan, T.; Hunter, L.; Smith RF (บรรณาธิการ). รายงานการประชุมนานาชาติครั้งที่สี่ว่าด้วยระบบอัจฉริยะสำหรับชีววิทยาโมเลกุล (PDF)สำนักพิมพ์ AAAI หน้า143–153 
  16. ↑ McCaskill JS (1990). "ฟังก์ชันการแบ่งส่วนสมดุลและความน่าจะเป็นของการจับคู่เบสสำหรับโครงสร้างทุติยภูมิของ RNA" Biopolymers . 29 ( 6– 7): 1105– 19. doi : 10.1002/bip.360290621 . hdl : 11858/00-001M-0000-0013-0DE3-9 . PMID 1695107 . S2CID 12629688 .  
  17. ↑ Juan V.; Wilson C. (1999). "การทำนายโครงสร้างทุติยภูมิของ RNA โดยอาศัยพลังงานอิสระและการวิเคราะห์เชิงวิวัฒนาการ" J. Mol. Biol . 289 (4): 935– 947. doi : 10.1006/jmbi.1999.2801 . PMID 10369773 . 
  18. ↑ Zuker M (2000). "การคำนวณโครงสร้างทุติยภูมิของกรดนิวคลีอิก" Curr. Opin. Struct. Biol . 10 (3): 303– 310. doi : 10.1016/S0959-440X(00)00088-9 . PMID 10851192 . 
  19. ↑ Mathews DH; Sabina J.; Zuker M.; Turner DH (1999). "การขยายการพึ่งพาของลำดับของพารามิเตอร์ทางอุณหพลศาสตร์ช่วยปรับปรุงการทำนายโครงสร้างทุติยภูมิของ RNA" . J. Mol. Biol . 288 (5): 911– 940. doi : 10.1006/jmbi.1999.2700 . PMID 10329189 . S2CID 19989405 .  
  20. 1 2 3 4 5 6 7 8 B. Knudsen & J. Hein. (2003). "Pfold: การทำนายโครงสร้างทุติยภูมิของ RNA โดยใช้ไวยากรณ์แบบไร้บริบทเชิงสุ่ม" . Nucleic Acids Research . 31 (13): 3423– 3428. doi : 10.1093/nar/gkg614 . PMC 169020 . PMID 12824339 .  
  21. 1 2 3 Knudsen B.; Hein J. (1999). "การทำนายโครงสร้างทุติยภูมิของ RNA โดยใช้ไวยากรณ์แบบไร้บริบทเชิงสุ่มและประวัติวิวัฒนาการ" . Bioinformatics . 15 (6): 446– 454. doi : 10.1093/bioinformatics/15.6.446 . PMID 10383470 . 
  22. ↑ Rivas E.; Eddy SR (2001). "การตรวจจับยีน RNA ที่ไม่เข้ารหัสโดยใช้การวิเคราะห์ลำดับเปรียบเทียบ" . BMC Bioinformatics . 2 (1): 8. doi : 10.1186/1471-2105-2-8 . PMC 64605 . PMID 11801179 .  
  23. ↑ Holmes I .; Rubin GM (2002). การเปรียบเทียบโครงสร้าง RNA แบบคู่ด้วยไวยากรณ์แบบไร้บริบทเชิงสุ่มหน้า163–174 doi : 10.1142 /9789812799623_0016 ISBN  978-981-02-4777-5. PMID 11928472 . {{cite book}}: |journal=ละเลย ( ช่วยเหลือ )
  24. 1 2 P. P. Gardner; J. Daub; J. Tate; BL Moore; IH Osuch; S. Griffiths-Jones; RD Finn; EP Nawrocki; DL Kolbe; SR Eddy; A. Bateman. (2011). "Rfam: Wikipedia, clans and the "decimal" release" . Nucleic Acids Research . 39 (Suppl 1): D141– D145. doi : 10.1093/nar/gkq1129 . PMC 3013711 . PMID 21062808 .  
  25. ↑ Yao Z.; Weinberg Z.; Ruzzo WL (2006). "CMfinder - อัลกอริทึมการค้นหาโมทีฟ RNA ตามแบบจำลองความแปรปรวนร่วม" . Bioinformatics . 22 (4): 445– 452. doi : 10.1093/bioinformatics/btk008 . PMID 16357030 . 
  26. ↑ Rabani M.; Kertesz M.; Segal E. (2008). "การทำนายเชิงคำนวณของโมทีฟโครงสร้าง RNA ที่เกี่ยวข้องกับกระบวนการควบคุมหลังการถอดรหัส" Proc . Natl. Acad. Sci. USA . 105 (39): 14885– 14890. Bibcode : 2008PNAS..10514885R . doi : 10.1073/pnas.0803169105 . PMC 2567462 . PMID 18815376 .  
  27. ↑ Goodarzi H.; Najafabadi HS; Oikonomou P.; Greco TM; Fish L.; Salavati R.; Cristea IM; Tavazoie S. (2012). "การค้นพบอย่างเป็นระบบขององค์ประกอบโครงสร้างที่ควบคุมความเสถียรของอาร์เอ็นเอส่งสารในสัตว์เลี้ยงลูกด้วยนม" Nature . 485 ( 7397): 264– 268. Bibcode : 2012Natur.485..264G . doi : 10.1038/nature11013 . PMC 3350620 . PMID 22495308 .  
  28. ↑ Sipser M. (1996). บทนำสู่ทฤษฎีการคำนวณ . สำนักพิมพ์ Brooks Cole.
  29. ↑ Michael A. Harrison (1978). บทนำสู่ทฤษฎีภาษาเชิงรูปธรรม . Addison-Wesley.
  30. ↑ Hopcroft JE; Ullman JD (1979). บทนำสู่ทฤษฎีออโตมาตา ภาษา และการคำนวณ Addison-Wesley.
  31. ↑ Giegerich R. (2000). "การอธิบายและควบคุมความกำกวมในการเขียนโปรแกรมเชิงพลวัต" การจับคู่รูปแบบ เชิงคอมบินาทอริก บันทึกการบรรยายในวิทยาการคอมพิวเตอร์ เล่มที่ 1848 ในรายงานการประชุม สัมมนา ประจำปีครั้งที่ 11 เรื่องการจับคู่รูปแบบเชิงคอมบินาทอริก 1848 บรรณาธิการโดย: Giancarlo R., Sankoff D. มอนทรีออ ลประเทศแคนาดา: Springer-Verlag, เบอร์ลิน หน้า46–59 doi : 10.1007/3-540-45123-4_6 ISBN   978-3-540-67633-1S2CID 17088251​​ 
  32. 1 2 3 Lari K.; Young SJ (1990). "การประมาณไวยากรณ์แบบไร้บริบทเชิงสุ่มโดยใช้อัลกอริทึมภายใน-ภายนอก" Computer Speech and Language . 4 : 35– 56. doi : 10.1016/0885-2308(90)90022-X .
  33. 1 2 3 Lari K.; Young SJ (1991). "การประยุกต์ใช้ไวยากรณ์แบบบริบทอิสระเชิงสุ่มโดยใช้อัลกอริทึมภายใน-ภายนอก" Computer Speech and Language . 5 (3): 237– 257. doi : 10.1016/0885-2308(91)90009-F .
  34. ↑ Nawrocki EP, Eddy SR (2013). "การค้นหาความคล้ายคลึงของ RNA ที่เร็วขึ้น 1.1 เท่า" . Bioinformatics . 29 (22): 2933– 2935. doi : 10.1093/bioinformatics/btt509 . PMC 3810854 . PMID 24008419 .  
  35. ↑ Tavaré S. (1986). "ปัญหาความน่าจะเป็นและสถิติบางประการในการวิเคราะห์ลำดับดีเอ็นเอ" การบรรยายเกี่ยวกับคณิตศาสตร์ในวิทยาศาสตร์ชีวภาพ สมาคมคณิตศาสตร์อเมริกัน 17 : 57– 86 .
  36. ↑ Muse SV (1995). "การวิเคราะห์เชิงวิวัฒนาการของลำดับดีเอ็นเอภายใต้ข้อจำกัดของโครงสร้างทุติยภูมิ"พันธุศาสตร์ 139 ( 3): 1429– 1439. doi : 10.1093/genetics/139.3.1429 . PMC 1206468 . PMID 7768450 .  
  37. ↑ Schöniger M.; von Haeseler A. (1994). "แบบจำลองเชิงสุ่มสำหรับการวิวัฒนาการของลำดับดีเอ็นเอที่มีความสัมพันธ์กันเอง" Mol. Phylogenet. Evol . 3 (3): 240– 7. Bibcode : 1994MolPE...3..240S . doi : 10.1006/mpev.1994.1026 . PMID 7529616 . 
  38. ↑ Baker, JK (1979). "ไวยากรณ์ที่ฝึกฝนได้สำหรับการรู้จำเสียงพูด"วารสารของสมาคมเสียงแห่งอเมริกา 65 ( S1): S132. Bibcode : 1979ASAJ...65Q.132B . doi : 10.1121/1.2017061 .
  39. 1 2 Searls, D (2013). "บทวิจารณ์: บทนำเกี่ยวกับภาษาศาสตร์โมเลกุลขนาดใหญ่" Biopolymers . 99 (3): 203– 217. doi : 10.1002/bip.22101 . PMID 23034580 . S2CID 12676925 .  
  40. ↑ Krogh, A; Brown, M; Mian, I; Sjolander, K; Haussler, D (1994). "แบบจำลองมาร์คอฟที่ซ่อนอยู่ในการชีววิทยาเชิงคำนวณ: การประยุกต์ใช้กับการสร้างแบบจำลองโปรตีน" J Mol Biol . 235 (5): 1501– 1531. doi : 10.1006/jmbi.1994.1104 . PMID 8107089 . S2CID 2160404 .  
  41. ↑ซิกริสต์, ซี; เซรุตติ, แอล; ฮูโล เอ็น; แกตติเกอร์, เอ; ฟัลเกต์, แอล; ปาคนี, เอ็ม; ไบโรช, เอ; บูเชอร์, พี (2002) "PROSITE: ฐานข้อมูลเอกสารที่ใช้รูปแบบและโปรไฟล์เป็นตัวอธิบายบรรทัดฐาน " ไบโออินฟอร์มโดยย่อ3 (3): 265– 274. ดอย : 10.1093/bib/3.3.265 . PMID 12230035 . 
  • ฐานข้อมูล Rfam
  • นรก
  • Stanford Parser: โปรแกรมวิเคราะห์ข้อมูลเชิงสถิติ
  • pyStatParser
  • QSMM – ตัวแยกวิเคราะห์แบบปรับตัวได้ทั้งจากบนลงล่างและจากล่างขึ้นบนสำหรับการเหนี่ยวนำ PCFG โดยใช้เทมเพลต

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ไม่มีชื่อบทความ

ใน ภาษาศาสตร์เชิงทฤษฎี และ ภาษาศาสตร์เชิง คำนวณ ไวยากรณ์บริบทอิสระเชิงความน่าจะเป็น ( PCFGs ) เป็นส่วนขยาย ของไวยากรณ์บริบทอิสระ คล้ายกับที่ แบบจำลองมาร์คอฟแบบซ่อน เร้นขยาย...

คำจำกัดความ

การสร้างสตริงแบบวน ซ้ำ: กระบวนการสร้างสตริงจากไวยากรณ์โดยใช้ การเรียกซ้ำ

คำจำกัดความอย่างเป็นทางการ

เช่นเดียวกับไวยากรณ์ แบบบริบทอิสระ (CFG) ไวยากรณ์แบบบริบทอิสระเชิงความน่าจะเป็น G สามารถกำหนดได้ด้วยชุดห้าองค์ประกอบ:

ความสัมพันธ์กับแบบจำลองมาร์คอฟที่ซ่อนอยู่

แบบจำลอง PCFG ขยาย ไวยากรณ์แบบไร้บริบท ในลักษณะเดียวกับที่ แบบจำลองมาร์คอฟแบบซ่อนเร้น ขยาย ไวยากรณ์แบบ ปกติ