Maximum-scoring segment sets

被引：15

作者：

Csürös, M ^{[1
]}

机构：

[1] Univ Montreal, Dept Informat & Rech Operat, Montreal, PQ H3C 3J7, Canada

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2004年 / 1卷 / 04期

关键词：

segmentation; change point estimation; noncoding RNA; thermophiles;

D O I：

10.1109/TCBB.2004.43

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

We examine the problem of finding maximum-scoring sets of disjoint segments in a sequence of scores. The problem arises in DNA and protein segmentation and in postprocessing of sequence alignments. Our key result states a simple recursive relationship between maximum-scoring segment sets. The statement leads to fast algorithms for finding such segment sets. We apply our methods to the identification of noncoding RNA genes in thermophiles.

引用

页码：139 / 150

页数：12

共 39 条

[1] NEW LOOK AT STATISTICAL-MODEL IDENTIFICATION [J].

AKAIKE, H .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1974, AC19 (06) :716-723

[2] A new approach to sequence comparison:: normalired sequence alignment [J].

Arslan, AN ;

Egecioglu, Ö ;

Pevzner, PA .

BIOINFORMATICS, 2001, 17 (04) :327-337

[3] ALGORITHMS FOR THE OPTIMAL IDENTIFICATION OF SEGMENT NEIGHBORHOODS [J].

AUGER, IE ;

LAWRENCE, CE .

BULLETIN OF MATHEMATICAL BIOLOGY, 1989, 51 (01) :39-54

[4] A complete sequence of the T tengcongensis genome [J].

Bao, QY ;

Tian, YQ ;

Li, W ;

Xu, ZY ;

Xuan, ZY ;

Hu, SN ;

Dong, W ;

Yang, J ;

Chen, YJ ;

Xue, YF ;

Xu, Y ;

Lai, XQ ;

Huang, L ;

Dong, XZ ;

Ma, YH ;

Ling, LJ ;

Tan, HR ;

Chen, RS ;

Wang, J ;

Yu, J ;

Yang, HM .

GENOME RESEARCH, 2002, 12 (05) :689-700

[5] The minimum description length principle in coding and modeling [J].

Barron, A ;

Rissanen, J ;

Yu, B .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (06) :2743-2760

[6]

BEMENT TR, 1977, MATH GEOL, V9, P55

[7]

Bentley J., 1984, Communications of the ACM, V27, P865, DOI 10.1145/358234.381162

[8]

Braun JV, 1998, STAT SCI, V13, P142

[9] The Ribonuclease P Database [J].

Brown, JW .

NUCLEIC ACIDS RESEARCH, 1999, 27 (01) :314-314

[10]

CHURCHILL GA, 1989, B MATH BIOL, V51, P79

← 1 2 3 4 →