Abstract
In this paper we consider the minimum weight multicolored subgraph problem (MWMCSP), which is a common generalization of minimum cost multiplex PCR primer set selection and maximum likelihood population haplotyping. In this problem one is given an undirected graph G with non-negative vertex weights and a color function that assigns to each edge one or more of n given colors, and the goal is to find a minimum weight set of vertices inducing edges of all n colors. We obtain improved approximation algorithms and hardness results for MWMCSP and its variant in which the goal is to find a minimum number of vertices inducing edges of at least k colors for a given integer k≤ n.
Chapter PDF
Similar content being viewed by others
References
Fernandes, R., Skiena, S.: Microarray synthesis through multiple-use PCR primer design. Bioinformatics 18, S128–S135 (2002)
Clark, A.: The role of haplotypes in candidate gene studies. Genet. Epid. 27, 321–333 (2004)
Bonizzoni, P., Vedova, G.D., Dondi, R., Li, J.: The haplotyping problem: An overview of computational models and solutions. Journal of Computer Science and Technology 18, 675–688 (2003)
Halldorsson, B., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., Istrail, S.: A survey of computational methods for determining haplotypes. In: Proc. of the DIMACS/RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotype Inference, pp. 26–47 (2004)
Niu, T.: Algorithms for inferring haplotypes. Genet. Epid. 27, 334–347 (2004)
Halperin, E., Hazan, E.: HAPLOFREQ - estimating haplotype frequencies efficiently. In: Proc. 9th Annual International Conference on Research in Computational Molecular Biology, pp. 553–568 (2005)
Gusfield, D.: Haplotyping by pure parsimony. In: Proc. 14th Annual Symp. on Combinatorial Pattern Matching, pp. 144–155 (2003)
Lancia, G., Pinotti, C., Rizzi, R.: Haplotyping populations: complexity and approximations. Technical Report DIT-02-0080, University of Trento (2002)
Wang, L., Xu, Y.: Haplotype inference by maximum parsimony. Bioinformatics 19, 1773–1780 (2003)
Brown, D., Harrower, I.: A New Integer Programming Formulation for the Pure Parsimony Problem in Haplotype Analysis. In: Proc. 4th International Workshop on Algorithms in Bioinformatics, pp. 254–265 (2004)
Lancia, G., Pinotti, M., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS Journal on Computing 16, 348–359 (2004)
Konwar, K., Măndoiu, I., Russell, A., Shvartsman, A.: Improved algorithms for multiplex PCR primer set selection with amplification length constraints. In: Proc. 3rd Asia-Pacific Bioinformatics Conference, pp. 41–50 (2005)
Hassin, R., Segev, D.: The set cover with pairs problem. In: Proc. 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 164–176 (2005)
Huang, Y.T., Chao, K.M., Chen, T.: An approximation algorithm for haplotype inference by maximum parsimony. Journal of Computational Biology 12, 1261–1274 (2005)
Slavik, P.: Improved performance of the greedy algorithm for partial cover. Information Processing Letters 64, 251–254 (1997)
Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. Journal of Algorithms 53, 55–84 (2004)
Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)
Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 136–145 (2004)
Feige, U.: Relations between average case complexity and approximation complexity. In: Proc. 34th Annual ACM Symposium on Theory of Computing, pp. 534–543 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hajiaghayi, M.T., Jain, K., Lau, L.C., Măndoiu, I.I., Russell, A., Vazirani, V.V. (2006). Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science – ICCS 2006. ICCS 2006. Lecture Notes in Computer Science, vol 3992. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758525_102
Download citation
DOI: https://doi.org/10.1007/11758525_102
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34381-3
Online ISBN: 978-3-540-34382-0
eBook Packages: Computer ScienceComputer Science (R0)