Trợ giúp về thuật toán cần thiết

Question

Tôi có một tập hợp các chuỗi (ví dụ: 10000 chuỗi) và tạo ma trận (10000x10000) thể hiện sự giống nhau hai chiều giữa hai trình tự. Bây giờ, mục tiêu là truy xuất tập hợp con (ví dụ 1000 chuỗi) từ tập hợp lớn và đảm bảo tính tương tự hai chiều giữa hai chuỗi trong tập con này nằm trong phạm vi (ví dụ: 50% ~ 85%).

Có thuật toán nhanh nào để thực hiện điều đó không?

Answer 1

Bạn có thể chuyển đổi này cho vấn đề lý thuyết đồ thị:

1. Mỗi dãy là một nút
2. Nếu giống nhau của hai nút là trong phạm vi nhất định hơn là một cạnh giữa chúng
3. Mục tiêu của bạn là để tìm số lượng lớn connected component (nếu mối quan hệ tương tự của bạn là transitive ...) hoặc số lượng lớn clique (... nếu không).

Answer 2

Bạn có thể tạo danh sách được sắp xếp tương tự theo cặp (tham chiếu về ma trận), lấy tập con của danh sách đã sắp xếp đó, sau đó đảm bảo rằng giao điểm giữa danh sách con đó và tập hợp con của bạn có cùng kích thước với tập hợp con của bạn xác minh rằng tất cả các phần tử trong tập hợp con của bạn nằm trong phạm vi được chỉ định.

Yêu cầu nhiều thiết lập để tạo ma trận và rất nhiều không gian để tạo danh sách có thứ tự. Ít nhất, thiết lập ma trận của bạn là O (n^2).

Answer 3

Điều này nghe có vẻ như "phát hiện clique" đối với tôi; vấn đề quyết định clique là NP-complete.

Tùy thuộc vào số liệu thống kê đằng sau các điểm tương đồng của chuỗi của bạn, bạn có thể hài lòng với thuật toán xấp xỉ cho bài toán tối đa. Một thuật toán ngẫu nhiên thậm chí có thể đủ tốt cho bạn. Nhưng nói chung đây là một vấn đề rất khó khăn và bạn sẽ không thể làm được gì nhiều ngay cả đối với N = 100.

Answer 4

Rất nhiều điểm tương đồng tương đương hoặc liên quan đến, một sản phẩm chấm trong một chiều không gian không gian, ngay cả khi sự tương đồng không được tính toán một cách rõ ràng như vậy. Trong những trường hợp này, và có thể là những người khác, có khả năng giá trị cao của a.b và b.c ngụ ý giá trị cao của a.c, nhưng ràng buộc cho giá trị này không phải là rất tốt - không tốt như tôi nghĩ lúc đầu.

Chỉ với ba vectơ liên quan - a, b, và c Tôi nghĩ rằng bạn có thể vẽ sơ đồ 3 chiều bất kể kích thước của không gian cơ bản và tôi nghĩ trường hợp xấu nhất là mặt phẳng, với b và c ở trên b. Trong trường hợp đó, ví dụ: cho tất cả các vectơ đơn vị và a.b = b.c = 0,9, một khoảng 25 độ trên b và c là khoảng 25 độ bên dưới nó, và a.c = 0,62. Trong thực tế cho ac = bc = x trong trường hợp này, ac = 2x^2 - 1.

Trong những trường hợp này, nếu tôi hoàn toàn phải giải quyết vấn đề cụ thể này, tôi sẽ thử tìm kiếm lại để liệt kê các tập hợp các nút rất gần đến một nút cụ thể. Bạn có thể, ví dụ, bắt đầu với hai nút tương tự nhất, và sau đó chạy một tìm kiếm, ở mỗi cấp độ, thêm nút chưa được thử gần nhất với một trong các nút gốc ban đầu. Hoặc bạn có thể xây dựng một nhóm liên kết đơn và kiểm tra tất cả các subtrees của nó với kích thước yêu cầu.