Tăng Tốc Giải Thuật BWA-MEM Trên Nền Tảng Phần Cứng

Luận văn thạc sĩ nghiên cứu máy tính tăng tốc giải thuật bwa mem trên nền tảng phần cứng, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực .

• Tác giả: Lưu Hữu Quyết
• Người hướng dẫn: TS. Phạm Quốc Cường
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Tăng Tốc Giải Thuật BWA-MEM Trên Nền Tảng Phần Cứng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới Thiệu Chung Về Tăng Tốc BWA MEM Trên Phần Cứng

Ngày nay, việc nghiên cứu các vấn đề liên quan đến sinh học và công nghệ gen ngày càng được đẩy mạnh. Với sự trợ giúp của tin sinh học, việc phân tích trình tự gen trở nên dễ dàng hơn. Dữ liệu về trình tự sinh học rất lớn, đòi hỏi thời gian và độ chính xác cao. Vì vậy, việc phát triển các giải thuật so sánh tuần tự trong lĩnh vực này là rất quan trọng. BWA-MEM là một giải thuật so trùng và sắp hàng chính xác, nhanh chóng với độ dài genome lớn. Đề tài này tập trung vào việc tăng tốc BWA-MEM bằng cách sử dụng nền tảng phần cứng để cải thiện hiệu năng BWA-MEM.

1.1. Tổng Quan Về Giải Thuật BWA và Ứng Dụng Trong Tin Sinh Học

Giải thuật BWA (Burrows-Wheeler Aligner) là một phần mềm được sử dụng rộng rãi trong tin sinh học để ánh xạ chuỗi DNA ngắn lên một bộ gen tham chiếu lớn. Giải thuật này có nhiều biến thể khác nhau, trong đó BWA-MEM được khuyến nghị cho các truy vấn chất lượng cao. Nó tối ưu hóa BWA-MEM để đảm bảo tính chính xác và tốc độ. Nhiều ứng dụng thực tiễn của BWA-MEM bao gồm xác định các biến thể di truyền, phát hiện đột biến và nghiên cứu sự tiến hóa của các loài. Dữ liệu trình tự sinh học có thể lên tới 120GB, chứa khoảng 9 Gbase, theo NCBI.

1.2. Tại Sao Cần Tăng Tốc Giải Thuật Ánh Xạ Chuỗi DNA BWA MEM

Dữ liệu DNA sequencing ngày càng tăng với tốc độ chóng mặt, đòi hỏi các phương pháp xử lý song song hiệu quả hơn. Việc tăng tốc các giải thuật sinh học, đặc biệt là BWA-MEM, có thể giảm đáng kể thời gian phân tích dữ liệu, từ đó thúc đẩy các nghiên cứu genomics và ứng dụng lâm sàng. Việc tối ưu hóa BWA-MEM sẽ có ý nghĩa quan trọng. Đồng thời, tăng tốc phần cứng cũng là một hướng đi đầy tiềm năng. Theo luận văn gốc, việc phân tích, tìm kiếm, so sánh trong dữ liệu gen lớn đòi hỏi nhiều thời gian và tính chính xác.

II. Thách Thức và Giới Hạn Hiệu Năng Của Giải Thuật BWA

Mặc dù BWA-MEM là một giải thuật hiệu quả, nó vẫn gặp phải những thách thức về hiệu năng khi xử lý lượng dữ liệu lớn. Các yếu tố như băng thông bộ nhớ và tính toán phức tạp có thể làm chậm quá trình ánh xạ chuỗi DNA. Việc tối ưu hóa BWA-MEM để đáp ứng nhu cầu ngày càng tăng của ngành tin sinh học là rất quan trọng. Các phương pháp truyền thống như tối ưu hóa phần mềm có thể không đủ, và việc sử dụng nền tảng phần cứng có thể mang lại hiệu quả đáng kể.

2.1. Phân Tích Bottleneck Hiệu Năng Của BWA MEM Trên CPU Truyền Thống

Việc chạy BWA-MEM trên CPU truyền thống có thể gặp phải các vấn đề về băng thông bộ nhớ và khả năng xử lý song song hạn chế. Điều này đặc biệt đúng khi xử lý các bộ dữ liệu lớn. Phân tích các điểm nghẽn về hiệu năng BWA-MEM giúp xác định các phần của giải thuật cần được tối ưu hóa hoặc chuyển sang nền tảng phần cứng phù hợp hơn. Theo luận văn, việc sử dụng các công cụ hỗ trợ từ tin học giúp công việc nghiên cứu trở nên dễ dàng và đảm bảo được sự chính xác cao.

2.2. Ảnh Hưởng Của Băng Thông Bộ Nhớ Đến Tốc Độ Giải Thuật BWA MEM

Băng thông bộ nhớ là một yếu tố quan trọng ảnh hưởng đến tốc độ của giải thuật BWA. Việc truy xuất dữ liệu từ bộ nhớ có thể trở thành một điểm nghẽn, đặc biệt khi xử lý các bộ dữ liệu lớn. Các giải pháp tăng tốc phần cứng như FPGA và GPU có thể cung cấp băng thông bộ nhớ cao hơn, giúp giảm thiểu ảnh hưởng của yếu tố này. Các công cụ hỗ trợ từ tin học sẽ đảm bảo được sự chính xác cao, hỗ trợ công tác nghiên cứu về sinh học đặc biệt là công nghệ gen.

III. Tăng Tốc BWA MEM Bằng FPGA Hướng Tiếp Cận và Lợi Ích

FPGA (Field Programmable Gate Array) là một lựa chọn phổ biến để tăng tốc phần cứng cho BWA-MEM. Với khả năng tùy biến cao, FPGA cho phép tối ưu hóa kiến trúc phần cứng để phù hợp với các yêu cầu cụ thể của giải thuật. Việc sử dụng VHDL hoặc Verilog để lập trình FPGA cho phép kiểm soát tối đa hiệu năng BWA-MEM. Tăng tốc với FPGA mang lại hiệu năng cao nhưng đòi hỏi kiến thức chuyên sâu về thiết kế phần cứng.

3.1. Thiết Kế Kiến Trúc Phần Cứng Tối Ưu Cho BWA MEM Trên FPGA

Việc thiết kế kiến trúc phần cứng tối ưu trên FPGA đòi hỏi sự hiểu biết sâu sắc về giải thuật BWA. Các kỹ thuật như xử lý song song và pipelining có thể được sử dụng để cải thiện hiệu năng. Kiến trúc phần cứng cần được thiết kế để tận dụng tối đa băng thông bộ nhớ và giảm thiểu độ trễ. Theo luận văn, có nhiều giải thuật xếp trình tự gen như BWA-MEM, Bowtie2, Cushaw2, GEM, AGILE, STELLR và mỗi giải thuật đều có những ưu điểm và nhược điểm riêng.

3.2. Sử Dụng VHDL Verilog Để Hiện Thực Giải Thuật BWA MEM Trên FPGA

VHDL và Verilog là các ngôn ngữ mô tả phần cứng được sử dụng để lập trình FPGA. Việc sử dụng các ngôn ngữ này cho phép kiểm soát chính xác các hoạt động của phần cứng. Tuy nhiên, việc lập trình FPGA đòi hỏi kỹ năng chuyên môn cao và có thể mất nhiều thời gian. Ngôn ngữ VHDL hoặc Verilog cho phép kiểm soát tối đa hiệu năng BWA-MEM.

IV. Phương Pháp Tăng Tốc BWA MEM Bằng GPU Ưu Điểm và Cách Triển Khai

GPU (Graphics Processing Unit) là một lựa chọn khác để tăng tốc BWA-MEM. Với hàng ngàn lõi tính toán, GPU có thể thực hiện xử lý song song hiệu quả. CUDA và OpenCL là các nền tảng lập trình GPU phổ biến, cho phép các nhà phát triển tận dụng sức mạnh tính toán của GPU. Tăng tốc với GPU dễ dàng triển khai hơn so với FPGA, nhưng có thể không đạt được hiệu năng BWA-MEM cao nhất.

4.1. Tối Ưu Hóa Kernel Tính Toán BWA MEM Cho Kiến Trúc GPU

Việc tối ưu hóa kernel tính toán cho GPU là rất quan trọng để đạt được hiệu năng tối đa. Các kỹ thuật như coalesced memory access và shared memory có thể giúp giảm thiểu độ trễ và cải thiện băng thông bộ nhớ. Việc lựa chọn thuật toán phù hợp cũng có thể ảnh hưởng đáng kể đến hiệu năng. Hiện thực song song hóa một chương trình là cả một thử thách mới.

4.2. Sử Dụng CUDA OpenCL Để Lập Trình Tăng Tốc BWA MEM Trên GPU

CUDA và OpenCL là các nền tảng lập trình GPU phổ biến. CUDA được phát triển bởi NVIDIA và tương thích với các GPU NVIDIA, trong khi OpenCL là một tiêu chuẩn mở và có thể chạy trên nhiều loại GPU khác nhau. Lập trình GPU đòi hỏi sự hiểu biết về kiến trúc GPU và các kỹ thuật tối ưu hóa. Đề tài này sử dụng CUDA.

V. Đánh Giá Hiệu Năng và So Sánh Các Nền Tảng Tăng Tốc BWA MEM

Việc đánh giá hiệu năng BWA-MEM là rất quan trọng để xác định hiệu quả của các phương pháp tăng tốc. Các tiêu chí đánh giá bao gồm thời gian thực thi, mức tiêu thụ điện năng và độ chính xác của kết quả. Việc so sánh các nền tảng phần cứng khác nhau giúp xác định lựa chọn phù hợp nhất cho các ứng dụng cụ thể. Dữ liệu thực nghiệm và các kết quả nghiên cứu sẽ cung cấp thông tin chi tiết về hiệu năng BWA-MEM của từng nền tảng.

5.1. Tiêu Chí Đánh Giá Hiệu Năng Thời Gian Điện Năng Độ Chính Xác

Các tiêu chí đánh giá hiệu năng BWA-MEM cần được xác định rõ ràng trước khi tiến hành thực nghiệm. Thời gian thực thi là một tiêu chí quan trọng, nhưng mức tiêu thụ điện năng và độ chính xác của kết quả cũng cần được xem xét. Việc đánh đổi giữa các tiêu chí này có thể cần thiết để đạt được hiệu năng BWA-MEM tổng thể tốt nhất.

5.2. So Sánh FPGA GPU CPU Ưu Nhược Điểm Trong Tăng Tốc BWA MEM

Mỗi nền tảng phần cứng có những ưu điểm và nhược điểm riêng. FPGA cung cấp khả năng tùy biến cao và hiệu năng BWA-MEM tốt, nhưng đòi hỏi kiến thức chuyên sâu về thiết kế phần cứng. GPU dễ dàng triển khai hơn, nhưng có thể không đạt được hiệu năng BWA-MEM cao nhất. CPU là lựa chọn đơn giản nhất, nhưng có thể không đáp ứng được yêu cầu hiệu năng BWA-MEM trong nhiều trường hợp.

VI. Kết Luận và Hướng Phát Triển Trong Tăng Tốc Giải Thuật BWA MEM

Việc tăng tốc BWA-MEM là một lĩnh vực nghiên cứu quan trọng trong tin sinh học. Các phương pháp tăng tốc phần cứng như FPGA và GPU có thể mang lại hiệu quả đáng kể. Tuy nhiên, việc lựa chọn nền tảng phù hợp và tối ưu hóa giải thuật là rất quan trọng. Các nghiên cứu trong tương lai có thể tập trung vào việc khám phá các kiến trúc phần cứng mới và các kỹ thuật tối ưu hóa tiên tiến hơn.

6.1. Tổng Kết Kết Quả Nghiên Cứu và Đề Xuất Giải Pháp Tối Ưu

Tổng kết lại các kết quả nghiên cứu và đưa ra các đề xuất về giải pháp tối ưu cho từng ứng dụng cụ thể. Việc xem xét các yếu tố như yêu cầu hiệu năng BWA-MEM, ngân sách và kỹ năng chuyên môn là rất quan trọng để lựa chọn giải pháp phù hợp nhất.

6.2. Hướng Nghiên Cứu Tương Lai Để Nâng Cao Hiệu Năng BWA MEM

Đề xuất các hướng nghiên cứu trong tương lai để tiếp tục nâng cao hiệu năng BWA-MEM. Các lĩnh vực tiềm năng bao gồm phát triển các kiến trúc phần cứng mới, áp dụng các kỹ thuật tối ưu hóa tiên tiến và khám phá các giải thuật ánh xạ chuỗi DNA mới.

Trích đoạn nội dung tài liệu

Chương 1 GIỚI THIỆU ĐỀ TÀI 1.1 Tổng quan vấn đề Ngày nay, đứng trước nguy cơ đối mặt với những vấn đề sức khỏe nghiêm trọng, con người ngày càng đẩy mạnh nghiên cứu đối với các vấn đề liên quan đến sinh học và công nghệ gen nhằm tìm ra những giải pháp cho các vấn đề trên. Trong những năm qua, với sự trợ giúp của những ngành khoa học khác, ngành sinh học và công nghệ gen đã gặt hái được nhiều thành tựu đáng kể, đặc biệt là sự chuyển dịch từ cấu trúc của các đa phân tử sinh học sang phân tích trình tự sinh học. Theo dữ liệu về các trình tự sinh học có tại National Center for Biotechnology Information (NCBI) của Mỹ, đã có tới 120GB chứa khoảng 9 Gbase (Gbase hay còn gọi là Giga base pairs là một cặp bazơ gồm 2 nucleotid đối ngược nhau trong chuỗi xoắn kép) [1]. Việc phân tích, tìm kiếm, so sánh,.

trong dữ liệu gen lớn như vậy đòi hỏi nhiều thời gian cũng như tính chính xác trong quá trình thực thi, do đó việc phát triển các giải thuật so sánh tuần tự trong lĩnh vực sinh học là khá quan trọng. Qua đó ta thấy lĩnh vực máy tính cũng góp phần không nhỏ đối với lĩnh vực sinh học. Bằng việc sử dụng các công cụ hỗ trợ từ tin học, công việc nghiên cứu trở nên dễ dàng và đảm bảo được sự chính xác cao, từ đó giúp cho công tác nghiên cứu về sinh học đặc biệt là công nghệ gen.2 Động lực nghiên cứu Sắp xếp trình tự gen mang đến nhiều lợi ích: • Phát hiện được bệnh tế bào máu hình lưỡi liềm [2]. • Thiết kế các peptide kháng thể [3].

• Xét nghiệm di truyền [4]. • Xác định quan hệ tiến hóa loài [4]. Trong đề tài này, chúng tôi chọn GPU (thay vì chọn nền tảng FPGA, Multi- core, .) để tăng tốc thuật toán xếp trình tự gen bởi GPU có nhiều core nên phù hợp để thử nghiệm. Mặt khác, quá trình thiết lập môi trường thử nghiệm dễ dàng và ngôn ngữ được sử dụng để lập trình GPU (cụ thể là dùng CUDA) là C/C++.

Tuy nhiên, việc sử dụng ngôn ngữ C/C++ lập trình cho GPU không hề đơn giản so với lập trình tuần tự đơn thuần. Nói cách khác, việc tiếp cận và hiện thực song song hóa một chương trình là cả một thử thách mới đối với chúng tôi khi tiếp cận vấn đề này. Hiện nay có nhiều giải thuật xếp trình tự gen như BWA-MEM [5], Bowtie2 [6], Cushaw2 [7], GEM [8], AGILE [9], STELLR [10],. và mỗi giải thuật đều có những ưu điểm và nhược điểm riêng.

Tuy nhiên trong đề tài này, chúng tôi quyết định chọn giải thuật BWA- MEM, vì đó là một giải thuật so trùng và sắp hàng một cách chính xác, nhanh chóng trong trình tự sinh học với độ dài genome lớn, cân bằng tốt (scale well) đối với vộ genome lớn và đặc biệt là mã nguồn mở (điều này dễ dàng trong việc tìm hiểu và hiện thực giải thuật trên nền tảng GPU).3 Đóng góp của đề tài Đề tài có các đóng góp sau. Phân tích cấu trúc chương trình BWA-MEM. Tăng tốc chương trình BWA-MEM trên nền tảng GPU.4 Cấu trúc của luận văn Luận văn được chia thành 8 chương theo cấu trúc như sau: 1. Giới thiệu tổng quan các vấn đề trong Sinh-Tin học, động lực nghiên cứu, đóng góp của đề tài và trình bày cấu trúc luận văn.

Các kiến thức nền tảng được trình bày trong giải thuật BWA-MEM như: Burrows-Wheeler Transform (BWT), Full-text index Minute-space (FM- index), giải thuật Smith-Waterman (SW) và kiến thức nền tảng GPU, CUDA. Phân tích cấu trúc chương trình BWA-MEM. Tìm hiểu các công trình liên quan đến đề tài, quan sát và nhận định. Trình bày ý tưởng và cách thức hiện thực chương trình trên GPU, 6.

Trình bày kết quả thực nghiệm, đánh giá và phân tích kết quả. Trình bày về kết luận vấn đề các giới hạn và công việc tiếp theo của đề tài trong tương lai. Tài liệu tham khảo. 3 Chương 2 KIẾN THỨC NỀN TẢNG Chương 2 trình bày tổng quan các kiến thức về kỹ thuật Burrows-Wheeler Transform (BWT), Full-text Minute-space (FM-index), giải thuật Smith-Waterman (SW) và GPU (Graphics Processing Unit).

Đồng thời cũng cấp kiến thức về Burrows-Wheeler Aligner (BWA-MEM) - một trong những giải thuật so trùng và sắp hàng chuỗi với độ dài lớn từ 70bp đến vài megabases. Những kiến thức này đặc biệt quan trọng bởi nó giúp chúng ta biết được cách thức hoạt động của giải thuật BWA-MEM để từ đó thực hiện giải thuật BWA-MEM trên GPU nhằm tăng tốc cho giải thuật BWA-MEM.1 Kiến Thức Nền Tảng Được Sử Dụng Trong BWA-MEM 2.1 Burrows-Wheeler Transform (BWT) Giải thuật được sử dụng trong kỹ thuật nén dữ liệu theo ý tưởng sắp xếp lại các ký tự trong một chuỗi để tạo ra một chuỗi có nhiều các ký tự giống nhau dồn lại với nhau hơn chuỗi ban đầu và có thể chuyển đổi từ chuỗi này lại chuỗi ban đầu. Thuật toán tạo ra chuỗi BWT có thể mô tả như sau với chuỗi abaaba. Ta kí hiệu chuỗi abaaba là T.

Bước 1: Viết thêm vào cuối T một kí tự là $ (đại diện cho con trỏ EOF), xét n+1 hoán vị vòng quanh, ta được: 4 abaaba$ baaba$a aaba$ab aba$aba ba$abaa a$abaab $abaaba Bước 2: Sắp xếp n+1 hoán vị vòng quanh đó theo thứ tự từ điển tạo thành ma trận BWT. $abaaba a$abaab aaba$ab aba$aba abaaba$ ba$abaa baaba$a Bước 3: Viết ra các ký tự cuối của các hoán vị vòng quanh theo đúng thứ tự sau khi đã sắp xếp tạo thành từ mã BWT của T: abba$aa Dưới đây Hình 2.1 sẽ mô tả tổng quan quá trình xây dựng chuỗi BWT.1: Tổng quan xây dựng chuỗi BWT [11] 5 2.2 Chuyển đổi về chuỗi gốc ban đầu: BWT-reversing Xét ma trận BWT (MT ) cột đầu và cột cuối ký hiệu là F và L, đánh thứ tự cho các ký tự ở 2 cột này. T bwt là chuỗi BWT được tạo ra từ MT. MT có tính chất "Last-to-First column mapping" (LF-mapping) nghĩa là sự xuất hiện thứ i của ký tự ở cột cuối cùng (L) tương ứng với sự xuất hiện thứ i của ký tự đó ở cột đầu tiên (F).

Theo [12], LF-mapping có: • C(·) biểu thị mảng chiều dài |Σ| sao cho C[c] chứa tổng số lần xuất hiện của các ký tự trong dữ liệu text có thứ tự từ điển nhỏ hơn ký tự c. LF(·) đại diện cho Last-to-First column mapping bởi vì ký tự T bwt [i] ở cột cuối L của ma trận MT sẽ nằm ở cột đầu F tại vị trí LF(i) và LF(·) cũng cho phép dò ngược chuỗi T. Cụ thể, nếu T[k] = T bwt [i] thì T[k-1] = T bwt [LF(i)]. Dựa vào Hình 2.1 ta có T bwt = "abba$aa".1: Thứ tự của các ký tự trong T bwt 1 2 3 4 5 6 7 T bwt a b b a $ a a • Xây dựng C[c] của T bwt Bảng 2.3: Occ(c,q) của T bwt a b b a $ a a 1 2 3 4 5 6 7 $ 0 0 0 0 1 1 1 a 1 1 1 2 2 3 4 b 0 1 2 2 2 2 2 LF(6) = C(a) + Occ(a,6) = 1 + 3 = 4 => L(6) = F(4) = a2 LF(4) = C(a) + Occ(a,4) = 1 + 2 = 3 => L(4) = F(3) = a1 LF(3) = C(b) + Occ(b,3) = 5 + 2 = 7 => L(3) = F(7) = b1 LF(7) = C(a) + Occ(a,7) = 1 + 4 = 5 => L(7) = F(5) = a3 LF(5) = C($) + Occ($,5) = 0 + 1 = 1 => L(5) = F(1) = $ Ta được chuỗi T = a3 b1 a1 a2 b0 a0 (Hình 2.2: LF-mapping [11] 7 Để chuyển về chuỗi gốc ban đầu, ta đảo ngược chuỗi bắt đầu từ phía phải của chuỗi gốc dò ngược về phía trái.

Cách thực hiện đảo ngược được trình bày như Hình 2. Kết quả thu được như sau: a3 b1 a1 a2 b0 a0 $ = T.3: BWT Reversing [11] Hình 2.4: Minh họa BWT Reversing trực quan [11] 2.3 FM-Index (Full-text index in Minute space) FM-index [13] cho phép tìm kiếm chuỗi con trùng một cách hiệu quả bên trong dữ liệu text. FM-index kết hợp kỹ thuật BWT với một vài cấu trúc dữ liệu phụ trợ để nhằm giảm bộ nhớ thực thi và thực hiện nhanh hơn. 8 Thành phần chính của FM-index bao gồm F (có thể được trình bày rất đơn giản 1 số nguyên cho 1 ký tự) và L (có thể nén được) từ ma trận BWT (Hình 2.

FM-index có khả năng tiết kiệm không gian cần để lưu trữ.5: Thành phần chính của FM-index [11] Truy vấn với FM-Index: việc truy vấn bằng cách sử dụng LF-mapping được mô tả như sau. • Ví dụ cần truy vấn chuỗi P = aba. Ta truy vấn như Hình 2. • Đã tìm được chuỗi P là có trong T và truy vấn này có cùng kết quả với mảng hậu tố (Hình 2.

Thuật toán cho FM-index [12]: xét chuỗi con trùng P[1,p] trong dữ liệu text T[1,n]. Giá trị occ là số lượng của những lần xuất hiện của chuỗi con trùng P[1,n] trong dữ liệu text nén T bwt. Hai thủ tục chính để vận hành FM- index: 1. Xác định số lượng của những lần xuất hiện của chuỗi con trùng P[1,p] trong dữ liệu nén T bwt sử dụng thuật toán get_row (Algorithm 1).

Tham số First trỏ đến hàng đầu tiên của ma trận BWT (MT ) chứa tiền tố P[i, p] và tham số Last trỏ đến hàng cuối của MT chứa tiền tố P[i, p]. Thuật toán trả về giá trị occ = Last - First + 1. Xác định những vị trí của của chuỗi con trùng P[1,n] ở trong dữ liệu text T sử dụng thuật toán get_position (Algorithm 2) trả về occ giá trị nguyên khác nhau trong khoảng [1,n].6: Các bước thực hiện truy vấn với FM-index [11] Hình 2.7: Vị trí trùng lắp trong BWT [11] 10 Algorithm 1 Thuật toán get_rows để tìm những hàng chứa tiền tố P[1,n] [12] Function GET_ROWS(P [1, p]) begin i ← p, c ← P ]p F irst ← C[c] + 1, Last ← C[c + 1]; while ((F irst ≤ Last) and (i ≥ 2)) do c ← P [i − 1]; F irst ← C[c] + Occ(c, F irst − 1) + 1; Last ← C[c] + Occ(c, Last); i ← i − 1; end if Last < F irst then return no rows pref ixed by P [1, p]; end else return (First,Last); end end Algorithm 2 Thuật toán get_position cho việc tính toán Pos(i) [12] Function GET_POSITION(i) begin i0 ← i, t ← 0; while row i’ is not marked do i0 ← LF [i0 ]; t ← t + 1; end return Pos(i’) + t; end Ví dụ: Truy vấn chuỗi P = aba trong dữ liệu text T = aabaaba. Dựa vào Hình 2.1 ta có T bwt = abba$aa.

Áp dụng tiến trình của FM-index.