Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms for RH mapping: New ideas and improved analysis
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 34, no 1, 89-108 p.Article in journal (Refereed) Published
Abstract [en]

Radiation hybrid ( RH) mapping is a technique for constructing a physical map describing the locations of n markers on a chromosome of an organism. In [J. Comput. Biol., 4 (1997), pp. 517-533], Ben-Dor and Chor presented new algorithms for the RH problem and gave the first performance guarantees for such algorithms. We improve the lower bounds on the number of experiments in a way that is sufficient for two of these algorithms to give a correct ordering of the markers with high probability. Not only are the new bounds tighter, but our analysis also captures to a much higher extent how the bounds depend on the actual arrangement of the markers. Furthermore, we modify the two algorithms to utilize RH mapping data produced with several radiation intensities. We show that the new algorithms are almost insensitive to the problem of using the correct intensity.

Place, publisher, year, edition, pages
2004. Vol. 34, no 1, 89-108 p.
Keyword [en]
RH mapping, algorithms, performance bounds, multiple intensities, radiation hybrid maps, genome
Identifiers
URN: urn:nbn:se:kth:diva-23948DOI: 10.1137/s0097539701388355ISI: 000225642600005Scopus ID: 2-s2.0-16244388946OAI: oai:DiVA.org:kth-23948DiVA: diva2:342647
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lagergren, Jens
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM journal on computing (Print)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf