Sharan Roded, Halldósson Bjarni V, Istrail Sorin
School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel.
Proc IEEE Comput Syst Bioinform Conf. 2005:65-72. doi: 10.1109/csb.2005.37.
We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very restricted cases. On the positive side, we identify islands of tractability for the problem, by focusing on instances with specific structure of haplotype sharing among the input genotypes. We exploit the structure of those instance to give polynomial and constant-approximation algorithms to the problem. We also show that the general parsimony haplotyping problem is fixed parameter tractable.
我们研究了用于单倍型推断的简约方法，该方法要求找到一组基数最小的单倍型，以解释输入的基因型集合。我们证明，即使在非常受限的情况下，该问题也是APX难的。从积极的方面来看，我们通过关注输入基因型之间具有特定单倍型共享结构的实例，确定了该问题的易处理区域。我们利用这些实例的结构，为该问题给出了多项式和常数近似算法。我们还表明，一般的简约单倍型分型问题是固定参数可处理的。
