У меня есть словарь, который содержит ключ в качестве подстроки и его значение в виде списка начальных и конечных индексов, в которых он появляется в последовательности. Я должен идентифицировать те ключи, которые дополнительно являются подстрокой другого ключа, и диапазоны индекса ключа меньшей длины лежат в пределах диапазона ключа большей длины. Например:
{'TGTGT': [(1, 5), (3, 7)], 'GTGT': [(2, 5), (4, 7), (38, 41)], 'GTCA': [(6, 9), (17, 20), (40, 43)], 'CATG': [(8, 11), (27, 30), (42, 45)], 'CATGCTACG': [(8, 16), (27, 35)], 'ATGCTACG': [(9, 16), (28, 35)], 'TGCTACG': [(10, 16), (29, 35)], 'GCTACG': [(11, 16), (30, 35)], 'CTACG': [(12, 16), (31, 35)], 'TACG': [(13, 16), (32, 35)], 'GTGTCATG': [(4, 11), (38, 45)], 'TGTCATG': [(5, 11), (39, 45)], 'GTCATG': [(6, 11), (40, 45)], 'TCATG': [(7, 11), (41, 45)], 'ATGT': [(0, 3), (43, 46)]}
для ключей 'TCATG' и 'GTCATG', 'TCATG' является подстрокой последней, и индексы диапазона ее, т. Е. (7, 11), (41, 45), находятся в пределах диапазонов 'GTCATG', т.е. (6, 11), (40, 45)
Точно так же и для других ключей.
Какой самый эффективный способ сделать это?