A Graph-Based Approach for the DNA Word Design Problem

被引：3

作者：

Luncasu, Victor ^{[1
]}

Raschip, Madalina ^{[1
]}

机构：

[1] Alexandru Ioan Cuza Univ, Fac Comp Sci, Iasi 700483, Romania

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2021年 / 18卷 / 06期

关键词：

DNA; Hamming distance; Computational modeling; Evolutionary computation; Genetic communication; DNA computing; DNA word design; maximum independent set; ALGORITHMS; SETS;

D O I：

10.1109/TCBB.2020.3008346

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

The aim of this paper is to improve the best known solution of an important problem, the DNA Word Design problem, which has its roots in Bioinformatics and Coding Theory. The problem is to design DNA codes that satisfy some combinatorial constraints. The constraints considered are: minimum Hamming distance, fixed GC content and the reverse complement Hamming distance. The problem is modeled as a maximum independent set problem. Existing complex approaches for the maximum independent set problem, suitable for large graphs, were tested. In order to tackle large instances, libraries for external memory computations and sampling techniques were investigated. Eventually, we succeed in finding good lower bounds for the instances that were analyzed.

引用

页码：2747 / 2752

页数：6

共 24 条

[11]

Limbachiya D., 2016, ARXIV160700266

[12]

Limbachiya D, 2018, IEEE INT SYMP INFO, P2401, DOI 10.1109/ISIT.2018.8437313

[13] On combinatorial DNA word design [J].

Marathe, A ;

Condon, AE ;

Corn, RM .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2001, 8 (03) :201-219

[14]

Metodi Amit, 2011, Principles and Practice of Constraint Programming - CP 2011. Proceedings of the 17th International Conference (CP 2011), P621, DOI 10.1007/978-3-642-23786-7_47

[15]

MONTEMANNI R, 2015, J APPL OPERATIONS RE, V7, P36

[16]

Sanders Peter, 2013, Experimental Algorithms 12th International Symposium, SEA 2013. Proceedings, P164, DOI 10.1007/978-3-642-38527-8_16

[17] Linear and nonlinear constructions of DNA codes with Hamming distance d and constant GC-content [J].

Smith, Derek H. ;

Aboluion, Niema ;

Montemanni, Roberto ;

Perkins, Stephanie .

DISCRETE MATHEMATICS, 2011, 311 (13) :1207-1219

[18] Subnets of scale-free networks are not scale-free: Sampling properties of networks [J].

Stumpf, MPH ;

Wiuf, C ;

May, RM .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2005, 102 (12) :4221-4224

[19]

Tomita E, 2010, LECT NOTES COMPUT SC, V5942, P191, DOI 10.1007/978-3-642-11440-3_18

[20]

Tulpan D., 2006, THESIS U BRIT COLUMB

← 1 2 3 →