Дизайн базы данных для хранения информации LCS?

Question

У меня есть таблица, которая содержит 2 столбца, одна является идентификатором, а другая - столбцом, содержащим длинные строки например.

Id strings 
1 AGTTAGGACCTTACTCTATATCTGTTCTGTTGGTATGGAG 
2 GTACTTGTATTCTGATATCTAGGGTTTTCTAATTACTTCTG 
3 GTATTCTCTTTCTAGCTGATCGTAATTAAATCTTATCTAA 

, когда пользователь выполняет поиск, я хотел бы найти самую длинную общую подпоследовательность в строке поиска, и все данные в таблице. Например. последовательность поиска

TCTGTTCTG

1. Its a 100% match, with the whole match found. 
2. The LCS is TCTGTTCTG, but with some gaps. 
3. The LCS is TCTGTTCT, with some gaps in BTW. 

Есть ли способ хранить информацию о матче, который, где именно он начал находить матч, а затем ДО, где он нашел матч, а затем где это началось снова и так далее? Итак, что я могу представить данные в некоторой степени этот формат

First one => 

AGTTAGGACCTTACTCTATATCTGTTCTGTTGGTATGGAG 
        ||||||||| 
        TCTGTTCTG 

Second one => 

GTACTTGTATTCTGATATCTAGGGTTTTCTAATTACTTCTG 
| || | ||||| 
T CT G TTCTG 

В основном каким-то образом я мог хранить это, начальную и конечную позицию для каждой последовательности для каждой подпоследовательности нашли, так что, когда я показывать эту страницу в будущем , Мне не нужно снова вычислять этот матч и как-то выбрать эти данные о начале и конце базы данных и просто показать это в указанном формате? Я знаю, вопрос может быть немного туманным, но, пожалуйста, дайте мне знать, как еще я могу разработать, если у вас есть какие-либо сомнения?

Answer 1

Первый случай достаточно легкий используя PATINDEX.

Случай 1:

select Id, PATINDEX('%TCTGTTCTG%', strings) FROM table 

Это должно вернуть Id всех матчей 'Full' и начальное положение матча.

Случай 2:

select id, PATINDEX('%T%C%T%G%T%T%C%T%G%', strings) FROM table 

Это один, как представляется, возвращает значение для частичного совпадения, не выбирает «лучший» частичное совпадение)

будет вернуться к нему, когда я могу, много края случаев из того, что я вижу. (Кромки: Что делать, если есть несколько полных совпадений, вам нужно вернуть совпадение с наименьшим количеством пробелов в нем или просто совпадением с пробелами? То же самое касается частичных совпадений)

Это должно дать вам начните, пока я думаю о остальном.