Selection of DNA markers

被引：1

作者：

Hoogeboom, Hendrik Jan ^{[1
]}

Kosters, Walter A. ^{[1
]}

Laros, Jeroen F. J. ^{[1
]}

机构：

[1] Leiden Univ, Leiden Inst Adv Comp Sci, NL-2333 CA Leiden, Netherlands

来源：

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS | 2008年 / 38卷 / 01期

关键词：

DNA; edit distance; primers; substrings; uniqueness;

D O I：

10.1109/TSMCC.2007.906060

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Given a genome, i.e., a long string over a fixed finite alphabet, the problem is to find short (dis)similar substrings. This computationally intensive task has many biological applications. We first describe an algorithm to detect substrings that have edit distances to a fixed substring at most equal to a given e. We then propose an algorithm that finds the set of all,substrings that have edit distances larger than e to all others. Several applications are given, where attention is paid to practical biological issues such as hairpins and GC percentage. An experiment shows the potential of the methods.

引用

页码：26 / 32

页数：7

共 18 条

[1] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
AHO, AV
CORASICK, MJ
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 333 - 340
[2] Efficient approximate dictionary look-up for long words over small alphabets
Arslan, AN
[J]. LATIN 2006: THEORETICAL INFORMATICS, 2006, 3887 : 118 - 129
[3] PREDICTING DNA DUPLEX STABILITY FROM THE BASE SEQUENCE
BRESLAUER, KJ
FRANK, R
BLOCKER, H
MARKY, LA
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1986, 83 (11) : 3746 - 3750
[4] Dieffenbach C.W., 1995, PCR PRIMER LAB MANUA
[5] Fischer I, 2003, LECT NOTES COMPUT SC, V2810, P208, DOI 10.1007/978-3-540-45231-7_20
[6] Primer design for large scale sequencing
Haas, S
Vingron, M
Poustka, A
Wiemann, S
[J]. NUCLEIC ACIDS RESEARCH, 1998, 26 (12) : 3006 - 3012
[7] On-line construction of compact directed acyclic word graphs
Inenaga, S
Hoshino, H
Shinohara, A
Takeda, M
Arikawa, S
Mauri, G
Pavesi, G
[J]. DISCRETE APPLIED MATHEMATICS, 2005, 146 (02) : 156 - 179
[8] Efficient primer design algorithms
Kämpke, T
Kieninger, M
Mecklenburg, M
[J]. BIOINFORMATICS, 2001, 17 (03) : 214 - 225
[9] Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024
[10] Levenshtein V.I., 1966, SOV PHYS DOKL, V10, DOI DOI 10.1109/TVCG.2012.323

← 1 2 →