Catalogo Articoli (Spogli Riviste)
OPAC HELP
Titolo: On the complexity of positional sequencing by hybridization
Autore: BenDor, A; Peer, I; Shamir, R; Sharan, R;
 Indirizzi:
 Tel Aviv Univ, Sch Comp Sci, IL69978 Tel Aviv, Israel Tel Aviv Univ Tel Aviv Israel IL69978 mp Sci, IL69978 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:
 10665277(2001)8:4<361:OTCOPS>2.0.ZU;2Q
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 DNA; OLIGONUCLEOTIDES; CHIPS;
 Keywords:
 positional sequencing by hybridization; complexity; Eulerian graphs; NPhardness; 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, IL69978 Tel Aviv, Israel Tel Aviv Univ Lenanon St Tel Aviv Israel IL69978 l Aviv, Israel



 Citazione:
 A. BenDor et al., "On the complexity of positional sequencing by hybridization", J COMPUT BI, 8(4), 2001, pp. 361371
Abstract
In sequencing by hybridization (SBH), one has to reconstruct a sequence from its llong substrings. SBH was proposed as an alternative to gelbased 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 NPcomplete if each substring has at most three possible positions. We also show that PSBH is NPcomplete 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