Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Tsukuba BB: A branch and bound algorithm for local multiple alignment of DNA and protein sequences
Autore:
Horton, P;
Indirizzi:
Real World Comp Partnership, Tsukuba, Ibaraki 3050032, Japan Real World Comp Partnership Tsukuba Ibaraki Japan 3050032 3050032, Japan
Titolo Testata:
JOURNAL OF COMPUTATIONAL BIOLOGY
fascicolo: 3, volume: 8, anno: 2001,
pagine: 283 - 303
SICI:
1066-5277(2001)8:3<283:TBABAB>2.0.ZU;2-S
Fonte:
ISI
Lingua:
ENG
Soggetto:
BINDING-SITES; PATTERNS;
Keywords:
sequence alignment; motif; branch and bound; DNA; protein;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Life Sciences
Citazioni:
18
Recensione:
Indirizzi per estratti:
Indirizzo: Horton, P Tsukuba Mitsui Bldg 16F, Tsukuba, Ibaraki 3050032, Japan Tsukuba Mitsui Bldg 16F Tsukuba Ibaraki Japan 3050032 32, Japan
Citazione:
P. Horton, "Tsukuba BB: A branch and bound algorithm for local multiple alignment of DNA and protein sequences", J COMPUT BI, 8(3), 2001, pp. 283-303

Abstract

In this paper we present a branch and bound algorithm for local gapless multiple sequence alignment (motif alignment) and its implementation. The algorithm uses both score-based bounding and a novel bounding technique based on the "consistency" of the alignment. A sequence order independent search tree is used in conjunction with a technique for avoiding redundant calculations inherent in the structure of the tree. This is the first program to exploit the fact that the motif alignment problem is easier for short motifs. Indeed, for a short fixed motif width, the running time of the algorithm is asymptotically linear in the size of the input. We tested the performance of the program on a dataset of 300 E. coli promoter sequences and a dataset of 85 lipocalin protein sequences. For a motif width of 4, the optimal alignment of the entire set of sequences can be found. For the more natural motif width of 6, the program can align 21 sequences of length 100, more than twice the number of sequences which can be aligned by the best previous exact algorithm. The algorithm can relax the constraint of requiring each sequence to be aligned, and align 105 of the 300 promoter sequences with a motif width of 6. For the lipocalin dataset, we introduce a technique for reducing the effective alphabet size with a minimal loss of useful information. With this technique, we show that the program can find meaningful motifsin a reasonable amount of time by optimizing the score over three motif positions.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 21/01/20 alle ore 06:52:58