ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

Approximating the double-cut-and-join distance between unsigned genomes

หน่วยงาน Nanyang Technological University, Singapore

รายละเอียด

ชื่อเรื่อง : Approximating the double-cut-and-join distance between unsigned genomes
นักวิจัย : Chen, Xin , Sun, Ruimin , Yu, Jiadong
คำค้น : -
หน่วยงาน : Nanyang Technological University, Singapore
ผู้ร่วมงาน : -
ปีพิมพ์ : 2554
อ้างอิง : Chen, X., Sun, R., & Yu, J. (2011). Approximating the double-cut-and-join distance between unsigned genomes. BMC Bioinformatics, 12(Suppl 9):S17. , 1471-2105 , http://hdl.handle.net/10220/17879 , http://dx.doi.org/10.1186/1471-2105-12-S9-S17
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : BMC bioinformatics
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

In this paper we study the problem of sorting unsigned genomes by double-cut-and-join operations, where genomes allow a mix of linear and circular chromosomes to be present. First, we formulate an equivalent optimization problem, called maximum cycle/path decomposition, which is aimed at finding a largest collection of edge-disjoint cycles/AA-paths/AB-paths in a breakpoint graph. Then, we show that the problem of finding a largest collection of edge-disjoint cycles/AA-paths/AB-paths of length no more than l can be reduced to the well-known degree-bounded k-set packing problem with k = 2l. Finally, a polynomial-time approximation algorithm for the problem of sorting unsigned genomes by double-cut-and-join operations is devised, which achieves the approximation ratio 13/9 + e ≈ 1.4444 + e, for any positive ε. For the restricted variation where each genome contains only one linear chromosome, the approximation ratio can be further improved to 69/49 + e ≈ 1.4082 + e.

บรรณานุกรม :
Chen, Xin , Sun, Ruimin , Yu, Jiadong . (2554). Approximating the double-cut-and-join distance between unsigned genomes.
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Chen, Xin , Sun, Ruimin , Yu, Jiadong . 2554. "Approximating the double-cut-and-join distance between unsigned genomes".
    กรุงเทพมหานคร : Nanyang Technological University, Singapore.
Chen, Xin , Sun, Ruimin , Yu, Jiadong . "Approximating the double-cut-and-join distance between unsigned genomes."
    กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2554. Print.
Chen, Xin , Sun, Ruimin , Yu, Jiadong . Approximating the double-cut-and-join distance between unsigned genomes. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2554.