|
|||||
|
|
A polynomial case of the parsimony haplotyping problem |
|
| Authors: | Giuseppe Lancia Romeo Rizzi |
| Institution: | a Dipartimento di Matematica e Informatica, Università di Udine, Via delle Scienze 206, 33100 Udine, Italy b Dipartimento di Informatica e Telecomunicazioni, Università di Trento, Italy |
| Abstract: | The parsimony haplotyping problem was shown to be NP-hard when each genotype had k?3ambiguous positions, while the case for k?2 was open. In this paper, we show that the case for k?2 is polynomial, and we give approximation and FPT algorithms for the general case of k?0 ambiguous positions. |
| Keywords: | Totally unimodular matrices Approximation algorithms Fixed parameter tractability Parsimony haplotyping Computational biology |
| 本文献已被 ScienceDirect 等数据库收录！ | |