Στην παρούσα διδακτορική διατριβή, ασχολούµαστε µε ζητήµατα που ανακύπτουν σε ασύρµατα δίκτυα επικοινωνίας, δηλ. δίκτυα που βασίζονται σε τηλεπικοινωνιακή υποδοµή όπως τα κυψελικά δίκτυα κινητής τηλεφωνίας, δίκτυα αυτόνοµων ασύρµατων εκποµπών όπως τα ασύρµατα δίκτυα τύπου ad hoc, κτλ. Τα ασύρµατα δίκτυα επικοινωνίας διαφόρων τύπων έχουν εξελιχθεί σηµαντικά τα τελευταία χρόνια. Ειδικότερα, τα ασύρµατα αδόµητα δίκτυα (ή αλλιώς ασύρµατα δίκτυα τύπου ad hoc) έχουν προσελκύσει το έντονο εν­διαφέρον της επιστηµονικής κοινότητας λόγω των πολλών εφαρµογών που έχουν κυρίως σε περιπτώσεις όπου δεν είναι δυνατή ή επιθυµητή η ολική ή µερική κάλυψη µέσω υποδοµής µε βάση την ενσύρµατη δικτύωση (π.χ., επι­κοινωνία σε δυσπρόσιτες ή αποµακρυσµένες περιοχές, φυσικές καταστροφές, στρατιωτικές εφαρµογές, κλπ.). ΄Οπως και στα παραδοσιακά ενσύρµατα δίκτυα, σηµαντικό πρόβληµα αποτελεί η εγκαθίδρυση σχηµάτων επικοινωνίας όπως διάδοση (broadcasting, multicasting), επικοινωνία όλων µε όλους (gossiping, all-to-all communica­tion), και επικοινωνία σε οµάδες (group communication). Για την επικοινω­νία απαιτείται η κατανάλωση ενέργειας στους κόµβους του δικτύου και, λαµβ.άνοντας υπόψη ότι τα αδόµητα ασύρµατα δίκτυα χρησιµοποιούν κόµβους µε περιορισµένα αποθέµατα ενέργειας, είναι απαραίτητη η ορθολογιστική χρήση αυτής της ενέργειας κατά την επικοινωνία. Αυτό µπορεί να σηµαίνει ότι είναι επιθυµητή είτε η ελαχιστοποίηση της συνολικής ενέργειας που κα­ταναλώνεται στους κόµβους του δικτύου για επικοινωνία ή η ελαχιστοποίηση της µέγιστης ενέργειας ώστε να επιτυγχάνεται όσο το δυνατό µεγαλύτερος χρόνος ζωής όλων των κόµβων του δικτύου. Στη διατριβή εξετάζουµε αλγόριθ­µους για την εγκαθίδρυση διαφορετικών σχηµάτων επικοινωνίας σε αδόµητα ασύρµατα δίκτυα όπου βασικό κριτήριο για την εκτίµηση της απόδοσής τους θα είναι η κατανάλωση ενέργειας που επιφέρουν στο δίκτυο. Μοντελοποιούµε τα δίκτυα µε ειδικά γραφήµατα και τα αντίστοιχα προβλήµατα επικοινωνίας σαν προβλήµατα συνδυαστικής βελτιστοποίησης στα γραφήµατα αυτά. Τα αποτελέσµατά µας περιλαµβάνουν νέους αλγόριθµους που βελτιώνουν προηγούµενα γνωστά σχετικά αποτελέσµατα και νέα κάτω φράγµατα. Με κεντρικό στόχο την αποδοτική κατανοµή ενέργειας σε ασύρµατα δίκτυα, η µελέτη µας έχει διττό χαρακτήρα: από τη µια πλευρά, ασχολούµαστε µε µε­λέτη και ανάλυση θεµελιωδών προβληµάτων της Θεωρητικής Επιστήµης των Υπολογιστών (όπως, π.χ., το πρόβληµα Κάλυψης µε Σύνολα). Τέτοια προβλήµατα, και ειδικές περιπτώσεις τους, παρουσιάζουν εξαιρετικό ενδιαφέρον αφού χρησιµοποιούνται (µεταξύ άλλων) συχνά για τη µοντελοποίηση προβλη­µάτων ενεργειακά αποδοτικής επικοινωνίας σε ασύρµατα δίκτυα. Επιπλέον, προτείνουµε και αναλύουµε νέους αλγόριθµους για συγκεκριµένα σενάρια επικοινωνίας σε σύγχρονα ασύρµατα δίκτυα. Από την άλλη πλευρά, µελετάµε και εκτιµούµε πειραµατικά την απόδοση αρκετών αλγορίθµων και τεχνικών (από τη βιβλιογραφία αλλά και νέων) για ενεργειακά αποδοτική επικοινωνία σε ασύρµατα δίκτυα. Ειδικότερα: Μελετάµε το πρόβληµα κάλυψης µε σύνολα και ενδιαφέρουσες παραλ­λαγές του. Παρουσιάζουµε νέους συνδυαστικούς προσεγγιστικούς αλγόριθµους για το πρόβληµα k-κάλυψης συνόλων. Προηγούµενες προσεγγίσεις έχουν βασισθεί σε επεκτάσεις του άπληστου αλγόριθµου µέσω αποδοτικού χειρισµού µικρών συνόλων. Οι νέοι αλγόριθµοι επεκτείνουν περαιτέρω τις προηγούµενες προσεγγίσεις χρησιµοποιώντας την ιδέα του υπολογισµού µεγάλων οµάδων στοιχείων και στη συνέχεια της οµαδοποίησής τους σε σύνολα µεγάλου µεγέθους. Τα αποτελέσµατά µας βελτιώνουν τα καλύτερα γνωστά φράγµατα προσέγγισης για το πρόβληµα k-κάλυψης συνόλων για κάθε τιµή του k >= 6. Η τεχνική που χρησιµοποιούµε για την ανάλυση παρουσιάζει επιπλέον ανεξάρτητα ενδιαφέρον: το πάνω φράγµα για τον παράγοντα προ­σέγγισης επιτυγχάνεται φράσσοντας την αντικειµενική τιµή ενός γραµµικού προγράµµατος η οποία ‘αποκαλύπτει’ το λόγο προσέγγισης του υπό εξέταση αλγορίθµου (factor-revealing). Παρουσιάζουµε έναν απλό αλγόριθµο για το πρόβληµα εύρεσης µέγιστου δάσους γεννητικού αστέρα. Λαµβάνουµε υπόψη το γεγονός ότι το πρόβληµα αποτελεί ειδική περίπτωση του συµπληρωµατικού προβλήµατος κάλυψης συ­νόλου και προσαρµόζουµε έναν αλγόριθµο των Duh και Furer για την επίλυ­σή του. Αποδεικνύουµε ότι ο αλγόριθµος αυτός υπολογίζει 193/240 που είναι περίπου ίσο με 0.804 ­προσεγγιστικά δάση γεννητικών αστέρων. Το αποτέλεσµα αυτό βελτιώνει ένα προηγούµενο άνω φράγµα µε τιµή 0.71 των Chen και άλλων. Αν και ο αλ­γόριθµος είναι καθαρά συνδυαστικός, η ανάλυσή µας ορίζει ένα γραµµικό πρόγραµµα που χρησιµοποιεί µια παράµετρο f το οποίο είναι επιλύσιµο για τιµές της παραµέτρου f που δεν είναι µικρότερες από το λόγο προσέγγισης του αλγορίθµου. Η ανάλυση είναι αυστηρή και, το ενδιαφέρον είναι ότι, µπορεί να εφαρµοστεί και σε συµπληρωµατικές εκδοχές του προβλήµατος κάλυψης συνόλου όπως η εξοικονόµηση χρωµάτων. Δίνει την ίδια εγγύηση προσέγγισης µε τιµή 193/240 που οριακά βελτιώνει το προηγούµενο γνω­στό κάτω φράγµα των Duh και Furer. Αποδεικνύουµε επίσης ότι, γενικά, µια φυσική κλάση αλγορίθµων τοπικής αναζήτησης δε δίνουν καλύτερα από 1/2-προσεγγιστικά δάση γεννητικών αστέρων. Μελετάµε προβλήµατα επικοινωνίας σε ασύρµατα δίκτυα που υποστηρί­ζουν πολλαπλά µέσα ασύρµατης διασύνδεσης. Σε τέτοια δίκτυα, δύο κόµβοι µπορούν να επικοινωνήσουν αν είναι αρκετά κοντά και διαθέτουν κάποιο κοινό µέσο ασύρµατης διασύνδεσης. Η ενεργοποίηση ενός µέσου ασύρµατης διασύνδεσης επιφέρει ένα κόστος που αντανακλά την ενέργεια που καταναλώ­νεται όταν κάποιος κόµβος χρησιµοποιεί το µέσο αυτό. Διακρίνουµε µεταξύ της συµµετρικής και της µη συµµετρικής περίπτωσης, µε βάση το κόστος ενεργοποίησης για κάθε ασύρµατο µέσο διασύνδεσης είναι το ίδιο για όλους τους κόµβους ή όχι. Για τη συµµετρική περίπτωση, παρουσιάζουµε έναν (3/2+ε)–προσεγγιστικό αλγόριθµο για το πρόβληµα πλήρους διασύνδεσης µε ελάχιστο κόστος ενεργοποίησης, βελτιώνοντας ένα προηγούµενο φράγµα µε τιµή 2. Για τη µη συµµετρική περίπτωση, αποδεικνύουµε ότι το πρόβληµα διασύνδεσης δεν είναι προσεγγίσιµο στα πλαίσια ενός παράγοντα υπολογα­ριθµικού ως προς το πλήθος των κόµβων και παρουσιάζουµε ένα λογαριθµι­κό προσεγγιστικό αλγόριθµο για µια γενικότερη περίπτωση που µοντελοποιεί την οµαδική επικοινωνία. Επίσης, µελετάµε αλγόριθµους για τον υπολογισµό αποδοτικών ως προς την ενέργεια δένδρων µετάδοσης (multicasting) σε ασύρµατα αδόµητα δί­κτυα. Τέτοιοι αλγόριθµοι είτε ξεκινούν από µια κενή λύση η οποία σταδιακά επαυξάνεται για να δώσει ένα δένδρο µετάδοσης (επαυξητικοί αλγόριθµοι ­augmentation algorithms) είτε λαµβάνουν σαν είσοδο ένα αρχικό δένδρο µε­τάδοσης και εκτελούν ‘περιπάτους ’ σε διαφορετικά δένδρα µετάδοσης για πεπερασµένο αριθµό βηµάτων µέχρι να επιτευχθεί κάποια αποδεκτή µείωση στην κατανάλωση της ενέργειας (αλγόριθµοι τοπικής αναζήτησης -local search algorithms). Εστιάζουµε τόσο σε επαυξητικούς αλγόριθµους όσο και σε αλγό­ριθµους τοπικής αναζήτησης και συγκεκριµένα έχουµε υλοποιήσει αρκετούς υπάρχοντες αλγόριθµους από τη βιβλιογραφία αλλά και νέους. Συγκρίνου­µε πειραµατικά τους αλγόριθµους αυτούς σε τυχαία γεωµετρικά στιγµιότυπα του προβλήµατος και επιτυγχάνουµε αποτελέσµατα όσον αφορά στην αποδο­τικότητα ως προς την ενέργεια των λύσεων που λαµβάνουµε. Παρουσιάζουµε επίσης αποτελέσµατα σχετικά µε το χρόνο εκτέλεσης των υλοποιήσεών µας. Επίσης διερευνούµε το κατά πόσον οι λύσεις που λαµβάνουµε από επαυ­ξητικούς αλγόριθµους µπορούν να βελτιωθούν µέσω αλγορίθµων τοπικής αναζήτησης. Τα αποτελέσµατά µας αποδεικνύουν ότι ένας από τους νέους αλγόριθµους που προτείνουµε και οι εκδοχές του επιτυγχάνουν τις πιο απο­δοτικές ενεργειακά λύσεις και µάλιστα πολύ γρήγορα και, επιπλέον, υποδεικ­νύουν ιδιότητες γεωµετρικών στιγµιοτύπων του προβλήµατος που συντελούν στη βελτιωµένη απόδοση των επαυξητικών αλγορίθµων. / In this dissertation, we study issues arising in wireless communication networks, i.e., networks based on telecommunication infrastructure like cellular wireless networks, networks of autonomous wireless transmitters like ad hoc wireless networks, and so on. Wireless networks have received significant attention during the recent years. Especially, ad hoc wireless networks for which unlike traditional wired networks or cellular wireless networks, no wired backbone infrastructure is installed emerged due to their potential applications in emergency disaster relief, battlefield, etc. Like in traditional wired networks, an important problem concerns the establishment of communication patterns like broadcasting, multicasting, gossiping, all-to-all communication, and group communication. Communication then requires energy consumption at network nodes, and given that in ad hoc wireless networks energy is a scarce resource, it is of paramount importance to use it efficiently when establishing communication patterns. In such a setting, it is usually pursued that either the total energy consumed at networks nodes or the maximum energy consumed at any network node is minimized so that the network lifetime is prolonged as long as possible. Herein, we present and analyze theoretically and experimentally algorithms for guaranteeing the establishment of various communication patterns in ad hoc wireless networks and evaluate their performance in terms of their energy-efficiency. We represent these networks using graphs and model the corresponding communication problems as combinatorial optimization problems in such graphs. Our results include new algorithms which improve previously known relevant results as well as new lower bounds. Our main objective being the efficient energy allocation in wireless networks, our study is of dual character: on the one hand, we study and analyze fundamental problems of Theoretical Computer Science (like, e.g., Set Cover); such problems, as well as special cases of them, are highly interesting since they usually model energy-efficient communication problems in wireless networks. Furthermore, we propose and analyse new algorithms for particular communication scenaria in modern wireless networks. On the other hand, we experimentally study and evaluate several algorithms and techniques (both from the literature and new ones) for energy-efficient communication in wireless networks.

No description available.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-11T17:36:54Z No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:21Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:27Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Made available in DSpace on 2016-10-21T13:03:34Z (GMT). No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) Previous issue date: 2016-08-12 / Não recebi financiamento / Cluster analysis is the organization of a collection of patterns into clusters based on similarity which is determined by using properties of data. Clustering techniques can be useful in a variety of knowledge domains such as biotechnology, computer vision, document retrieval and many others. An interesting area of biology involves the concept of microRNAs (miRNAs) that are approximately 22 nucleotide-long non-coding RNA molecules that play important roles in gene regulation. Clustering miRNA sequences can help to understand and explore sequences belonging to the same cluster that has similar biological functions. This research work investigates and explores seven unsupervised clustering algorithms based on graphs that can be divided into three categories: algorithm based on region of influence, algorithm based on minimum spanning tree and spectral algorithm. To assess the contribution of the proposed algorithms, data from miRNA families stored in the online miRBase database were used in the conducted experiments. The results of these experiments were presented, analysed and evaluated using clustering validation indexes as well as visual analysis. / A análise de agrupamento é uma organização de coleção de padrões em grupos, baseando-se na similaridade das propriedades pertencentes aos dados. A técnica de agrupamento pode ser utilizado em muitas áreas de conhecimento como biotecnologia, visão computacional, recuperação de documentos, entre outras. Uma área interessante da biologia envolve o conceito de microRNAs (miRNAs), que são moléculas não-codificadas de RNA com aproximadamente 22 nucleotídeos e que desempenham um papel importante na regulação dos genes. O agrupamento de sequências de miRNA podem ajudar em sua exploração e entendimento, pois as sequências que pertencem ao mesmo grupo possuem uma função biológica similar. Esse trabalho explora e investiga sete algoritmos de agrupamentos não-supervisionados baseados em grafos que podem ser divididos em três categorias: algoritmos baseados em região de influência, algoritmos baseados em árvore spanning minimal e algoritmo espectral. Para avaliar a contribuição dos algoritmos propostos, os experimentos conduzidos utilizaram os dados das famílias de miRNAs disponíveis no banco de dados denominado miRBase. Os resultados dos experimentos foram apresentados, analisados e avaliados usando índices de validação de agrupamento e análise visual.

On-chip impedance tuning is used to overcome IC perturbations caused by packaging stress. Tuning is more important for matching networks of radio frequency (RF) systems. Possible package resonance and fabrication process variations may cause instability, which is a major problem in RF systems. Thus, precautions need to be taken in order to maintain the overall stability of components and the final system itself. Electrically erasable programmable read-only memory switches (EEPROMs) occupy less die area compared to e-fuses and microelectromechanical system (MEMS) switches, thus EEPROMs are proposed to be used as tuning switches in millimetre-wave (mm-wave) applications. It is anticipated that EEPROM switches will also enable multi-time programming because of the smaller area and the fact that more switches can be used for fine-tuning. The problem addressed in this research is how suitable EEPROMs are for switching applications in the mm-wave region. The main focus of this dissertation is to characterise the suitability of EEPROM switches qualitatively for tuning with systems operating in the mm-wave spectrum. 130 nm SiGe BiCMOS IBM 8HP process technology was used for simulation and the fabricated prototypes. The Dickson charge pump (CP), two voltage doubler CPs and four floating gate (FG) devices were investigated. Literature and theoretical verification was done using computer aided design (CAD) Cadence software through circuit analysis and the layouts were also designed for integrated circuit (IC) prototype fabrication. The qualitative evaluation of the hypothesis was based on investigating reliability issues, switching characteristics, CP output drive capability and mm-wave characterisation. The maximum measured drain current for FGs was 1.4 mA, 2.7 mA and 3 mA for devices 2, 3 and 4, respectively. The ratio between ON state switching current (after tunnelling) and OFF state switching current (after injection) was 1.5, 1.35 and 6 for devices 2, 3 and 4, respectively. The ratios correlated with the expected results in terms of FG transistor area: a high area results in a higher ratio. Despite the correlation, devices 2 and 3 may be unsuitable because the ratio is less than 2: a smaller ratio between the ON and OFF states could also result in higher losses. The Dickson CP achieved an output voltage of 2.96 V from an input of 1.2 V compared to 3.08 V as computed from the theoretical analysis and 4.5 V from the simulation results. The prototypes of the voltage doubler CP did not perform as expected: a maximum of 1 V was achieved compared to 4.1 – 5 V as in the simulation results. The suitability of FG devices for switching applications depends on the ratio of the ON and OFF states (associated to insertion and isolation losses): the larger the FG transistor area, the higher the ratio. The reliability issues are dominated by the oxide thickness of the transistor, which contributes to charge leakages and charge trapping: smaller transistor length causes more uncertainties. Charge trapping in the oxide increases the probability of leakages and substrate conduction, thus introduces more losses. Based on the findings of this research work, the FG devices promise to be suitable for mm-wave switching applications and there is a need for further research investigation to characterise the devices in the mm-wave region fully. AFRIKAANS : Impedansie-instelling op skyf word gebruik om steurings in geïntegreerde stroombane wat deur verpakkingstres veroorsaak word, te oorkom. Instelling is meer belangrik om netwerke van radiofrekwensiesisteme te paar. Moontlike verpakkingresonansie en variasies in die vervaardigingsproses kan onstabiliteit veroorsaak, wat ‟n groot probleem is in radiofrekwensiesisteme. Voorsorg moet dus getref word om die oorhoofse stabiliteit van komponente en die finale sisteem self te handhaaf. Elektries uitveebare programmeerbare slegs-lees-geheueskakelaars (EEPROMs) neem minder matrysarea op as e-sekerings en die sekerings van mikro-elektromeganiese sisteme en word dus voorgestel vir gebruik as instellingskakelaars in millimetergolfaanwendings. Daar word verwag dat EEPROM-skakelaars ook multi-tydprogrammering sal moontlik maak as gevolg van die kleiner area en die feit dat meer skakelaars gebruik kan word vir fyn instellings. Die probleem wat in hierdie navorsing aandag geniet, is die geskiktheid van EEPROMS vir skakelaanwendings in die millimetergolfstreek. The hooffokus van die verhandeling is om die geskiktheid van EEPROM-skakelaars kwalitatief te karakteriseer vir instelling met sisteme wat in die millimetergolfspektrum funksioneer. Department of Electrical, Electronic and Computer Engineering v University of Pretoria 130 nm SiGe BiCMOS IBM 8HP-prosestegnologie is gebruik vir simulasie en die vervaardigde prototipes. Die Dickson-laaipomp is gebruik vir simulasie en die vervaardigde prototipes. Die Dickson-laaipomp, twee spanningverdubbelinglaaipompe en vier swewendehektoestelle is ondersoek. Literatuur- en teoretiese verifikasie is gedoen met behulp van rekenaarondersteunde-ontwerp (CAD) Cadence-sagteware deur stroombaananalise en die uitleg is ook ontwerp vir die vervaardiging van geïntegreerdestroombaanprototipes. Die kwalitatiewe evaluasie van die hipotese is gebaseer op die ondersoek van betroubaarheidkwessies, skakelingeienskappe, laaipompuitsetdryfvermoë en millimetergolfkarakterisering. Die maksimum gemete dreineerstroom vir swewende hekke was 1.4 mA, 2.7 mA en 3 mA vir onderskeidelik toestelle 2, 3 en 4. Die verhouding tussen die AAN-toestand van die skakelstroom (na tonnelling) en die AF-toestand van die skakelstroom (na inspuiting) was 1.5, 1.35 en 6 vir toestelle 2, 3 en 4, onderskeidelik. Die verhoudings het ooreengestem met die verwagte resultate rakende die swewendehek-transistorareas: ‟n groot area het ‟n hoër verhouding tot gevolg. Nieteenstaande die ooreenstemming, mag toestelle 2 en 3 moontlik nie geskik wees nie, omdat die verhouding kleiner as 2 is: ‟n kleiner verhouding tussen die AAN- en AF-toestande mag ook hoër verliese tot gevolg hê. Die Dickson-laaipomp het ‟n uitsetspanning van 2.96 V vanaf ‟n inset van 1.2 V vergeleke met 3.08 V soos bereken volgens die teoretiese analise en 4.5 V volgens die simulasieresultate. Die prototipes van die spanningverdubbelinglaaipomp het nie gefunksioneer soos verwag is nie: ‟n maksimum van 1 V is bereik vergeleke met 4.1 – 5 V soos in die simulasieresultate. Die geskiktheid van swewendehektoestelle vir skakelingtoepassings hang af van die verhouding van die AAN- en AF-toestande (wat met invoer-en isolasieverlies geassosieer word): hoe groter die swewendehektransistorarea, hoe hoër die verhouding. Die betroubaarheidkwessies word oorheers deur die oksieddikte van die transistor, wat bydra tot ladinglekkasies en ladingvasvangs: korter transistorlengte veroorsaak meer onsekerheid. Ladingvasvangs in die oksied verhoog die moontlikheid van lekkasies en substraatgeleiding en veroorsaak dus groter verlies. Die bevindings van hierdie navorsing toon dat swewendehektoestelle waarskynlik geskik is vir millimetergolfaanwendings en verdere navorsing is nodig om die toestelle volledig in die millimetergolfstreek te karakteriseer. Copyright / Dissertation (MEng)--University of Pretoria, 2013. / Electrical, Electronic and Computer Engineering / unrestricted

Stem cells differentiate through an organized hierarchy of intermediate cell types to terminally differentiated cell types. This process is largely guided by master transcriptional regulators, but it also depends on the expression of many other types of genes. The discrete cell types in the differentiation hierarchy are often identified based on the expression or non-expression of certain marker genes. Historically, these have often been various cell-surface proteins, which are fairly easy to assay biochemically but are not necessarily causative of the cell type, in the sense of being master transcriptional regulators. This raises important questions about how gene expression across the whole genome controls or reflects cell state, and in particular, differentiation hierarchies. Traditional approaches to understanding gene expression patterns across multiple conditions, such as principal components analysis or K-means clustering, can group cell types based on gene expression, but they do so without knowledge of the differentiation hierarchy. Hierarchical clustering and maximization of parsimony can organize the cell types into a tree, but in general this tree is different from the differentiation hierarchy. Using hematopoietic differentiation as an example, we demonstrate how many genes other than marker genes are able to discriminate between different branches of the differentiation tree by proposing two models for detecting genes that are up-regulated or down-regulated in distinct lineages. We then propose a novel approach to solving the following problem: Given the differentiation hierarchy and gene expression data at each node, construct a weighted Euclidean distance metric such that the minimum spanning tree with respect to that metric is precisely the given differentiation hierarchy. We provide a set of linear constraints that are provably sufficient for the desired construction and a linear programming framework to identify sparse sets of weights, effectively identifying genes that are most relevant for discriminating different parts of the tree. We apply our method to microarray gene expression data describing 38 cell types in the hematopoiesis hierarchy, constructing a sparse weighted Euclidean metric that uses just 175 genes. These 175 genes are different than the marker genes that were used to identify the 38 cell types, hence offering a novel alternative way of discriminating different branches of the tree. A DAVID functional annotation analysis shows that the 175 genes reflect major processes and pathways active in different parts of the tree. However, we find that there are many alternative sets of weights that satisfy the linear constraints. Thus, in the style of random-forest training, we also construct metrics based on random subsets of the genes and compare them to the metric of 175 genes. Our results show that the 175 genes frequently appear in the random metrics, implicating their significance from an empirical point of view as well. Finally, we show how our linear programming method is able to identify columns that were selected to build minimum spanning trees on the nodes of random variable-size matrices.