Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
On the complexity of positional sequencing by hybridization
Autore:
Ben-Dor, A; Peer, I; Shamir, R; Sharan, R;
Indirizzi:
Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel Tel Aviv Univ Tel Aviv Israel IL-69978 mp Sci, IL-69978 Tel Aviv, Israel Univ Washington, Seattle, WA 98195 USA Univ Washington Seattle WA USA 98195 iv Washington, Seattle, WA 98195 USA
Titolo Testata:
JOURNAL OF COMPUTATIONAL BIOLOGY
fascicolo: 4, volume: 8, anno: 2001,
pagine: 361 - 371
SICI:
1066-5277(2001)8:4<361:OTCOPS>2.0.ZU;2-Q
Fonte:
ISI
Lingua:
ENG
Soggetto:
DNA; OLIGONUCLEOTIDES; CHIPS;
Keywords:
positional sequencing by hybridization; complexity; Eulerian graphs; NP-hardness; parameterized algorithms;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Life Sciences
Citazioni:
25
Recensione:
Indirizzi per estratti:
Indirizzo: Pe'er, I Tel Aviv Univ, Sch Comp Sci, Lenanon St, IL-69978 Tel Aviv, Israel Tel Aviv Univ Lenanon St Tel Aviv Israel IL-69978 l Aviv, Israel
Citazione:
A. Ben-Dor et al., "On the complexity of positional sequencing by hybridization", J COMPUT BI, 8(4), 2001, pp. 361-371

Abstract

In sequencing by hybridization (SBH), one has to reconstruct a sequence from its l-long substrings. SBH was proposed as an alternative to gel-based DNA sequencing approaches, but in its original form the method is not competitive. Positional SBH (PSBH) is a recently proposed enhancement of SBH in which one has additional information about the possible positions of each substring along the target sequence. We give a linear time algorithm for solving PSBH when each substring has at most two possible positions. On the other hand, we prove that the problem is NP-complete if each substring has at most three possible positions. We also show that PSBH is NP-complete if theset of allowed positions for each substring is an interval of length k andprovide a fast algorithm for the latter problem when k is bounded.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 19/01/20 alle ore 10:08:49