回答此问题可获得 20 贡献值，回答如果被采纳可获得 50 分。
<p>我正在为我的实习做一个药物遗传学分析。
对于这个剖析器，我需要确定患者最可能的单倍型。
到目前为止我所拥有的：</p>
<p>数据库中的单倍型定义，包含以下内容：</p>
<ul>
<li>单倍型名称</li>
<li>组成单倍型的等位基因/单核苷酸多态性列表</li>
<li>*单独-每个等位基因/单核苷酸多态性的位置（染色体、起始点、终止点）</li>
</ul>
<p>看起来有点像：</p>
<pre><code>...
['UGT1A1*16', 'T;A;T;C;G;A;G;C']
['UGT1A1*17', 'T;A;T;C>T;G;A;G;C']
...
</code></pre>
<p>每个等位基因（例如每个A、T、C或g）的位置如下：
<code>[6, 18130687, 18130687]</code>表示<code>[chromosome, start, stop]</code>，例如<code>C>G</code>表示参考位置是C，但是这个单倍型定义的区别是它是G而不是C</p>
<p>然后我检查了所有这些位置，看看病人在这些位置有哪些等位基因。由于一个人在每个位置都有两个等位基因，我得到如下结果：</p>
<pre><code>UGT1A1 = ['T-T', 'A-A', 'T-T', 'C-T', 'C-G', 'A-A', 'G-G','C-C']
</code></pre>
<p>格式为：<code>'<allele_1>-<allele_2>'</code>等位基因1和等位基因2可以互换。（我不知道哪些等位基因属于同一类，因为我没有分阶段信息）</p>
<p>现在我需要以最理想的方式匹配我在病人身上观察到的等位基因。每对中的每一个等位基因都必须使用，而且每对只能使用一次。在我的例子中，我在第4对和第5对中有不同的等位基因<code>'C-T' and 'C-G'</code>，因此可以创建4种不同的单倍型，如：</p>
<pre><code>[T, A, T, C, C, A, G, C]
[T, A, T, C, G, A, G, C]
[T, A, T, T, C, A, G, C]
[T, A, T, T, G, A, G, C] <-- the same as UGT1A1*17
</code></pre>
<p>假设我现在选择一组等位基因是<code>TATTGAGC</code>，另一组必须是<code>TATCCAGC</code>。第一个与UGT1A1*17的单倍型相同，但另一个只有8个等位基因中的7个与任何其他单倍型重叠。
实际的数据集要大得多，单倍型等位基因长度可以超过200个等位基因，加上有10到100个不同的定义，最后但并非最不重要的是，有大约60个不同的基因（每一个都有这些单倍型定义）。你知道吗</p>
<p>那么，有没有一种有效的方法来获得组成单倍型的所有等位基因组合，同时允许最少的错配？你知道吗</p>
<p>如何做到这一点的提示是受欢迎的，如在；使用dicts的方式像。。。或者将某些信息转储到sql数据库中（以便在处理数据时节省内存）或其他类似的内容。你知道吗</p>
<p>谢谢你花时间通读这一切！你知道吗</p>
