Computational aspects of radiation hybrid mapping

by Ivansson, Lars

Radiation hybrid (RH) mapping is an important technique for constructing genome maps, giving the location of n markers on a chromosome. In 1997, Ben-Dor and Chor presented two algorithms for the RH problem, P-Order and K-Order, together with an upper bound on the number of experiments sufficient for these algorithms to construct the correct order of the markers with high probability. We improve the analysis of both algorithms, and obtain tighter performance bounds. We also modify P-Order and K-Order to allow for the use RH data produced with multiple intensities. We show that given data produced with O(log n) different intensities, the dependency of the intensity can be removed from the performance bound for these modified algorithms. Experimental results show that the modified algorithms indeed are more stable than the original algorithms, with respect to the choice of intensity. To make better use of the information contained in multiple intensity data, we construct the Korder-ML algorithm, which is a maximum likelihood version of K-Order. The evaluations of Korder-ML show that the performance is improved significantly when using multiple intensity data. Korder-ML using multiple intensity data also improves the results of the RHO algorithm, by Ben-Dor et al., run on single intensity data. Finally, the Korder-ML is successfully evaluated on real data. Matrix-To-Line? is the problem of, given a distance matrix finding an arrangement of n points on R+, such that the maximum difference between the specified and the actual distances is minimized. We show that if P ?= NP, Matrix-To-Line? cannot be approximated better than 7/5. Furthermore, we give a 2-approximation algorithm for the Matrix-To-Line?, and show that unless 3-colorable graphs can be colored with ?4/?? colors in polynomial time, it is impossible to approximate Matrix-To-Line? within 2 ? ? in polynomial time. The 2-approximation algorithm for Matrix-To-Line? can be used for the RH problem. We show that the arrangement produced by this algorithm converges to the true arrangement as the number of experiments increases; both physically and in distribution. Finally, using an information theoretical result, we give an upper bound on the convergence rate for any algorithm for the RH problem. ISBN 91-7170-639-9 • TRITA-NA-0019 • ISSN 0348-2952 • ISRN KTH/NA/R--00/19--SE iii iv Sammanfattning RH (radiation hybrid) mappning är en viktig metod för att kartlägga genom. M?alet är att bestämma läget för n s?a kallade markörer p?a en kromosom. 1997 presenterade Ben-Dor och Chor tv?a algorithmer för RH problemet: P-Order och K-Order, tillsammans med en övre gräns för det antal experiment som är tillräckligt för att dessa algoritmer med hög sannolikhet ska hitta den korrekta markörordningen. Vi förbättrar analysen av b?ada dessa algoritmer, och härleder striktare gränser för prestandan. Vi modifierar även P-Order och K-Order, s?a att de kan användas för RH-data som framställts med multipla intensiteter. Vi visar att givet data framställd med O(log n) olika intensiteter, s?a kan prestandans beroende av intensiteterna eliminieras för de modifierade algoritmerna. Experimentella resultat visar ocks?a att de modifierade algoritmerna verkligen är stabilare med avseende p?a intensitetsval än de ursprungliga algoritmerna. För att bättre kunna utnyttja den information som finns i RH-data producerad med multipla intensiteter har vi konsturerat Korder-ML algoritmen, som är en maximum-likelihood version av K-Order. Utvärderingen av Korder-ML visar att prestandan förbättras avsevärt d?a data framställd med multipla intensiteter används. Vi visar även att Korder-ML användandes multiple-intensitetsdata ger bättre resultat än RHO-programmet användandes en-intensitetsdata. Slutligen visar vi att Korder-ML fungerar utmärkt ocks?a p?a verklig data. Matrix-To-Line? är problemet att givet en avst?andsmatris hitta en utplacering av n punkter p?a R+ s?adan att den maximala avvikelsen mellan de specificerade och de faktiska avst?anden minimeras. Vi visar att om P ?= NP, s?a kan inte Matrix-To-Line? approximeras bättre än 7/5. Dessutom ger vi en 2- approximationsalgoritm för Matrix-To-Line?, och visar att om inte 3-färgbara grafer kan färgas med ?4/?? färger i polynomisk tid, s?a är det omöjligt att approximera Matrix-To-Line? inom 2 ? ? i polynomisk tid. 2-approximationsalgoritmen för Matrix-To-Line? kan användas p?a RH-problemet. Vi visar att utplaceringen framställd av denna algoritm konvergerar, b?ade fysiskt och i distribution, mot den verkliga utplaceringen, d?a antalet experiment ökar. Slutligen ger vi med hjälp av ett informationsteoretiskt resultat en övre gräns för konvergenshastigheten för varje algoritm för RH-problemet. ISBN 91-7170-639-9 • TRITA-NA-0019 • ISSN 0348-2952 • ISRN KTH/NA/R--00/19--SE v vi