Thuật toán nhanh để tìm các bộ duy nhất trong hai chuỗi văn bản rất dài

Question

Tôi cần so sánh trình tự DNA của nhiễm sắc thể X và Y, và tìm các mẫu (gồm khoảng 50-75 cặp cơ sở) duy nhất cho nhiễm sắc thể Y. Lưu ý rằng các phần trình tự này có thể lặp lại trong nhiễm sắc thể. Điều này cần được thực hiện nhanh chóng (BLAST mất 47 ngày, cần vài giờ hoặc ít hơn). Có bất kỳ thuật toán hoặc chương trình nào đặc biệt phù hợp với loại so sánh này không? Một lần nữa, tốc độ là chìa khóa ở đây.

Một trong những lý do tôi đưa điều này lên SO là có được quan điểm từ những người bên ngoài miền ứng dụng cụ thể, người có thể đưa ra các thuật toán họ sử dụng trong so sánh chuỗi trong sử dụng hàng ngày của họ. Vì vậy, đừng ngại!

Answer 1

1. Xây dựng một suffix tree S trên dãy X.
2. Đối với mỗi vị trí bắt đầu i trong dãy Y, tìm kiếm chuỗi Y [i..i + 75] trong S. Nếu không phù hợp có thể được tìm thấy bắt đầu từ vị trí i (nghĩa là nếu tra cứu thất bại sau j < 75 nucleotide phù hợp) thì bạn đã tìm thấy một chuỗi dài-j duy nhất cho Y.
3. Chuỗi nhỏ nhất trên tất cả các vị trí bắt đầu i là chuỗi ngắn nhất (hoặc chỉ dừng lại sau khi bạn tìm bất kỳ chuỗi nào như vậy nếu bạn không quan tâm đến việc giảm thiểu độ dài).

Tổng thời gian: O (| X | + m | Y |) trong đó m là độ dài chuỗi tối đa (ví dụ: m = 75).

Có lẽ thậm chí có nhiều thuật toán hiệu quả hơn dựa trên cây hậu tố tổng quát.

Answer 2

Điều này paper có thể có một số lựa chọn thay thế để điều chỉnh BLAST để cải thiện hiệu suất của nó (bằng cách chia nhỏ không gian vấn đề AFAIKS).

Answer 3

Tôi giả định rằng bạn có một X và một Y đơn lẻ để so sánh. Kết hợp chúng, được phân tách bằng ký tự điểm đánh dấu không xuất hiện trong một trong hai, để tạo thành ví dụ: Xoy. Bây giờ, hãy tạo thành http://en.wikipedia.org/wiki/Suffix_array trong thời gian tuyến tính.

Những gì bạn nhận được là một chuỗi con trỏ tới các vị trí trong chuỗi nối, nơi các con trỏ được bố trí sao cho các điểm mà chúng trỏ tới xuất hiện theo thứ tự bảng chữ cái trong mảng. Bạn cũng nhận được một mảng LCP, cho độ dài của tiền tố chung dài nhất được chia sẻ giữa hậu tố và hậu tố trực tiếp trước nó trong mảng, đó là hậu tố sắp xếp ít hơn nó. Đây thực tế là tiền tố chung dài nhất được chia sẻ giữa vị trí đó và chuỗi con ANY ít hơn, bởi vì bất kỳ thứ gì có tiền tố chung dài hơn và ít hơn chuỗi [i] sẽ sắp xếp giữa nó và chuỗi hiện tại [i - 1].

Bạn có thể biết chuỗi gốc mà con trỏ trỏ vào từ vị trí của nó, vì X đến trước Y. Bạn có thể cắt mảng thành các phần con xen kẽ của các con trỏ X và Y. Độ dài của tiền tố chung được chia sẻ giữa pos [i] và pos [i - 1] là lcp [i]. Độ dài của tiền tố được chia sẻ giữa pos [i] và pos [i-2] là min (lcp [i], lcp [i-1]). Vì vậy, nếu bạn bắt đầu ở giá trị Y ngay trước một phạm vi X, bạn có thể tính số ký tự của tiền tố giữa Y đó và tất cả X lần lượt bằng cách đẩy xuống phần, thực hiện thao tác tối thiểu ở mỗi bước. Tương tự, bạn có thể tính số ký tự của tiền tố được chia sẻ giữa tất cả các X đó và Y xuất hiện tiếp theo trong mảng hậu tố với chi phí một phút cho mỗi X. Ditto, tất nhiên cho phạm vi Y. Bây giờ, hãy thực hiện tối đa mỗi mục nhập để tìm ra tiền tố dài nhất được chia sẻ giữa mỗi vị trí trong X (hoặc Y) và bất kỳ vị trí nào trong Y (hoặc X).

Tôi nghĩ bạn muốn các phần tử bên trong X hoặc Y có tiền tố nhỏ được chia sẻ giữa nó và bất kỳ chuỗi con nào khác của giới tính khác, bởi vì chuỗi dài hơn một ký tự này bắt đầu từ cùng vị trí không xuất hiện trong tình dục chút nào.Tôi nghĩ rằng một khi bạn đã thực hiện các phép tính min() ở trên, bạn có thể giải nén N nền tảng tiền tố nhỏ nhất bằng cách sử dụng một đống để theo dõi N mục nhỏ nhất. Tôi nghĩ rằng mọi thứ ở đây đều mất thời gian tuyến tính trong | X | + | Y | (trừ khi N có thể so sánh với | X | hoặc | Y |).

Answer 4

Tôi có một câu trả lời thú vị, nó sẽ là một công nghệ. Ý tưởng chính là việc so sánh các chuỗi phụ nên được thực hiện trên GPU, bởi vì GPU của card video hiện đại là môi trường xử lý song song cao (như siêu máy tính nhỏ). Vì vậy, chúng ta có thể mã hóa cặp cơ sở thành một pixel, cho rằng nhiễm sắc thể X là 154 triệu đôi - chúng ta có một hình ảnh cho nhiễm sắc thể X bao gồm 154 triệu pixel - kích thước hình ảnh này sẽ là khoảng 500 MB. Đối với nhiễm sắc thể Y, chúng tôi nhận được hình ảnh có kích thước 160 MB. Vì vậy, hai hình ảnh MB (500 + 160) này có thể được xử lý bằng thẻ video gốc rất hiệu quả. (Chỉ cần có một card video với> = 1 GB ram video).

Bước tiếp theo là viết chương trình GPU, có lẽ với sự giúp đỡ của Pixel Shader hoặc Cuda hoặc OpenCL

chương trình GPU sẽ là rất đơn giản - về cơ bản nó sẽ so sánh 50-75 pixel lân cận theo hình ảnh của nhiễm sắc thể Y để tất cả các pixel của X hình ảnh nhiễm sắc thể. Vì vậy, chương trình GPU này sẽ có tối đa 75 * 154 triệu hoạt động, sẽ được tính trên GPU hiện đại trong HOUR trở lên. Bởi vì tất cả các chuỗi con của Y sẽ được kiểm tra song song.

hy vọng rằng sẽ giúp