Minimum Interval Cover and Its Application to Genome Sequencing
作者： Liang Ding , Bin Fu , Binhai Zhu
DOI: 10.1007/978-3-642-22616-8_23
关键词:
摘要: Pairwise end sequencing is a very useful method for whole genome which determines the complete DNA sequence of an organism's with help laboratory processes. Pairedend interval cover problem derived from pairwise sequencing. A paired-end S constituted at most two disjoint intervals, and can be described as given family F find least number pairedend intervals to S. We prove that NP-complete. The c-interval generalization allows each member have c intervals. It extends classical set-cover reasonably. show APX-hard when ≤ 3. For solving these problems, we present polynomial-time 6c-approximation algorithm fixed parameter tractable k-bounded problem. Our implementation results approximation ratio much smaller than theoretical bound real examples.
springer.com
sci-hub.st 参考文章(26)
S. RICHARDS, D.M. MUZNY, A.B. CIVITELLO, F. LU, R.A. GIBBS, CHAPTER TWENTY-EIGHT – Sequence Map Gaps and Directed Reverse Sequencing for the Completion of Large Sequencing Projects Automated DNA Sequencing and Analysis. pp. 191- 198 ,(1994) , 10.1016/B978-0-08-092639-1.50032-0
J. Craig Venter, Chris Fields, Mark D. Adams, Automated DNA sequencing and analysis. Academic Press. ,(1994)
J. C. Venter, GENOMICS: Shotgun Sequencing of the Human Genome Science. ,vol. 280, pp. 1540- 1542 ,(1998) , 10.1126/SCIENCE.280.5369.1540
F. Sanger, G. M. Air, B. G. Barrell, N. L. Brown, A. R. Coulson, J. C. Fiddes, C. A. Hutchison, P. M. Slocombe, M. Smith, Nucleotide sequence of bacteriophage φX174 DNA Nature. ,vol. 265, pp. 687- 695 ,(1977) , 10.1038/265687A0
Elad Hazan, Shmuel Safra, Oded Schwartz, On the complexity of approximating k -set packing Computational Complexity. ,vol. 15, pp. 20- 39 ,(2006) , 10.1007/S00037-006-0205-6
Robert D Fleischmann, Mark D Adams, Owen White, Rebecca A Clayton, Ewen F Kirkness, Anthony R Kerlavage, Carol J Bult, Jean-Francois Tomb, Brian A Dougherty, Joseph M Merrick, Keith McKenney, Granger Sutton, Will FitzHugh, Chris Fields, Jeannine D Gocayne, John Scott, Robert Shirley, Li-lng Liu, Anna Glodek, Jenny M Kelley, Janice F Weidman, Cheryl A Phillips, Tracy Spriggs, Eva Hedblom, Matthew D Cotton, Teresa R Utterback, Michael C Hanna, David T Nguyen, Deborah M Saudek, Rhonda C Brandon, Leah D Fine, Janice L Fritchman, Joyce L Fuhrmann, NSM Geoghagen, Cheryl L Gnehm, Lisa A McDonald, Keith V Small, Claire M Fraser, Hamilton O Smith, J Craig Venter, Whole-genome random sequencing and assembly of Haemophilus influenzae Rd. Science. ,vol. 269, pp. 496- 512 ,(1995) , 10.1126/SCIENCE.7542800
W. Fiers, R. Contreras, F. Duerinck, G. Haegeman, D. Iserentant, J. Merregaert, W. Min Jou, F. Molemans, A. Raeymaekers, A. Van den Berghe, G. Volckaert, M. Ysebaert, Complete nucleotide sequence of bacteriophage MS2 RNA: primary and secondary structure of the replicase gene. Nature. ,vol. 260, pp. 500- 507 ,(1976) , 10.1038/260500A0
Ran Raz, Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP symposium on the theory of computing. pp. 475- 484 ,(1997) , 10.1145/258533.258641
Craig A. Tovey, A SIMPLIFIED NP-COMPLETE SATISFIABILITY PROBLEM Discrete Applied Mathematics. ,vol. 8, pp. 85- 89 ,(1984) , 10.1016/0166-218X(84)90081-7
Ellson Y. Chen, David Schlessinger, Juha Kere, Ordered Shotgun Sequencing, a Strategy for Integrated Mapping and Sequencing of YAC Clones Genomics. ,vol. 17, pp. 651- 656 ,(1993) , 10.1006/GENO.1993.1385