GIảI THUậT SửA LỗI CHO CáC TRìNH Tự ADN NGắN

Abstract

Today with the development of DNA sequencing technology, we have obtained a large amount of DNA sequences in a short time with low cost. Specially, the next-generation DNA sequecing can generate a huge amount of short DNA sequences, called short reads with length from 30 to 100 bp. The short reads have an error rate between 1% and 2%. Therefore, the error reads must be corrected before being assembled into the complete genome. There are several proposed algorithms for correcting the error reads such as SHREC and SOAP de Novo. However, SHREC needs a long computation time to correct errors while SOAP de Novo requires very high memory usage. In this paper, we present our algorithm (RCorrector) based on the index structure of KMER for detecting and correcting error reads. Compared to the SHREC algorithm, the RCorrector algorithm provides a speed up from 3 to 7 with the same sensitivity and specificity.

Tóm tắt

Ngày nay với sự tiến bộ của kỹ thuật xác lập trình tự ADN (DNA Sequencing) chúng ta có thể tạo ra một số lượng lớn các chuỗi ADN trong khoảng thời gian ngắn với chi phí thấp. Đặc biệt thế hệ xác lập trình tự mới hiện nay tạo ra số lượng rất lớn chuỗi ADN ngắn, được gọi là short read, với chiều dài từ 30 đến 100 nulcotide. Các read này có tỉ lệ lỗi từ 1% đến 2%. Do đó các read lỗi này phải được sửa lỗi trước khi được lắp ráp thành bộ gien ADN hoàn chỉnh. Nhiều giải thuật sửa lỗi đã được đề xuất như SHREC, SOAP de Novo. Nhưng những giải thuật này vẫn còn những hạn chế như cần dung lượng bộ nhớ lớn hoặc thời gian sửa lỗi khá nhiều. Trong bài báo này chúng tôi đề xuất giải thuật hiệu chỉnh lỗi, được đặt tên là RCorrector, dựa trên cấu trúc chỉ mục kmer nhằm phát hiện lỗi và sửa lỗi trực tiếp trên các read. So sánh với giải thuật SHREC trên 8 tập dữ liệu, RCorrector đạt được hiệu suất sửa lỗi thông qua hai đặc trưng specificity và sensitivity là tương đương với SHREC nhưng nhanh hơn SHREC từ 3 đến 7 lần.