Для упражнения я должен определить наименьшее подмножество протеомов, содержащих все указанные белки. Объекты, с которыми я могу работать, выглядят так:Поиск минимального подмножества ключей из словаря списков
Словарь списков с идентификатором протеома в виде ключей и списком белковых идентификаторов белков, которые содержатся в нем. У меня также есть массив идентификаторов белков. Несколько протеомов могут иметь одинаковые идентификаторы белка.
Вопрос: Найдите наименьшее подмножество протеомов, содержащих все белки, объявленные в массиве.
Визуализация:
словарь списков
{'UP000040088': ['A0A0T9TGA2', 'A0A0T9PBK6'],'UP000005347': ['I2WKK5', 'I2W7Q9', 'I2WH23', 'I2W8G3', 'I2W8S8', 'I2WCH8', 'I2WCJ2', 'I2WA21', 'I2WC26', 'I2WCG9', 'I2W9F2', 'I2WKG5', 'I2W4G7', 'I2WCD6', 'I2WG92', 'I2W6I6', 'I2W648', 'I2WE51', 'I2WKU2', 'I2WIG4', 'I2WED9', 'I2WEM0', 'I2WB05', 'I2W998', 'I2W7Q9', 'I2WA37', 'I2WD89', 'I2WEB4', 'I2W4G7', 'I2W4B1', 'I2WIM9', 'I2WI84', 'I2WIS6', 'I2WES7', 'I2WGL9', 'I2WIA8', 'I2W7H0', 'I2WDB3', 'I2WE60', 'I2WC93', 'I2WC36', 'I2WC86', 'I2WC82', 'I2W6J9', 'I2W428', 'I2WCH8', 'I2WCJ2', 'I2W9T1', 'I2W9B9', 'I2WC26', 'I2WCG9', 'I2WA28', 'I2WA21', 'I2W648', 'I2WE51', 'I2WKU2', 'I2WIG4', 'I2WEM0', 'I2WED9', 'I2W9F2'], 'UP000001592': ['A9IMD2', 'A9IU64', 'A9IWM9', 'A9IWP5', 'A9IZ28', 'A9IZ30', 'A9IZ48', 'A9IZ71', 'A9IZ73', 'A9IZ75']}
массива
['A9IWM9', 'A9IWP5','A0A0T9PBK6']
Выход в этом примере должен быть
'UP000040088':['A0A0T9PBK6'],'UP000001592':['A9IWM9', 'A9IWP5']
наилучшими пожеланиями
Что вы уже пробовали? Вы сталкиваетесь с проблемами при кодировании? Просить рабочего решения не то, что SO для –
хорошо, я попробовал жадный метод, который выполняет итерацию массива и ищет первый ключ с правильным значением. Однако это, очевидно, не даст мне меньшее подмножество, а не просто подмножество. Я хотел бы получить некоторые идеи, как подойти к этой проблеме. – user3620381