No description available.

Indiana University-Purdue University Indianapolis (IUPUI) / Pharmacodynamics (PD) studies the relationship between drug concentration and drug effect on target sites. This field has recently gained attention as studies involving PD Drug-Drug interactions (DDI) assure discovery of multi-targeted drug agents and novel efficacious drug combinations. A PD drug combination could be synergistic, additive or antagonistic depending upon the summed effect of the drug combination at a target site. The PD literature has grown immensely and most of its knowledge is dispersed across different scientific journals, thus the manual identification of PD DDI is a challenge. In order to support an automated means to extract PD DDI, we propose Pharmacodynamics Miner (PD-Miner). PD-Miner is a text-mining tool, which is capable of identifying PD DDI from in vitro PD experiments. It is powered by two major features, i.e., collection of full text articles and in vitro PD ontology. The in vitro PD ontology currently has four classes and more than hundred subclasses; based on these classes and subclasses the full text corpus is annotated. The annotated full text corpus forms a database of articles, which can be queried based upon drug keywords and ontology subclasses. Since the ontology covers term and concept meanings, the system is capable of formulating semantic queries. PD-Miner extracts in vitro PD DDI based upon references to cell lines and cell phenotypes. The results are in the form of fragments of sentences in which important concepts are visually highlighted. To determine the accuracy of the system, we used a gold standard of 5 expert curated articles. PD-Miner identified DDI with a recall of 75% and a precision of 46.55%. Along with the development of PD Miner, we also report development of a semantically annotated in vitro PD corpus. This corpus includes term and sentence level annotations and serves as a gold standard for future text mining.

The field of classical planning deals with designing algorithms for generating plans or squences of actions that achieve specific goals. It involves representing a problem domain as a set of state variables, actions and goals, and then developing search algorithms that can explore the state of possible plans to find the one that satisfies the specified goal. Classical planning domains are often NP-hard, meaning that their worst-case complexity grows exponentially with the size of the problem. This means that as the number of state variables, actions and goals in the problem domain increases, the search space grows exponentially, making it very difficult to find a plan that satisfies the specified goal. This thesis is concerned with investigating these NP-hard domains, specifically by simplifying these domains into ones that have a polynomial solving time, creating a general policy of conditions and rules for which actions to take for the simplified domain, and then attempting to apply this policy onto the original domain. This creates a partial policy for the original domain, and the performance of this policy can be measured in order to judge its effectiveness. This can be explained as simplifying an intractable domain into a tractable one, creating a general policy for the tractable domain and then measuring its performance as a partial policy for the intractable domain.

Cette thèse aborde les facettes dynamiques des principes fondamentaux du problème de l'appariement stable plusieurs-à-un. Nous menons notre étude dans le contexte du choix de l'école et de l'appariement entre les hôpitaux et les résidents. Dans la première étude, en utilisant le modèle résident-hôpital, nous étudions la complexité de calcul de l'optimisation des variations de capacité des hôpitaux afin de maximiser les résultats pour les résidents, tout en respectant les contraintes de stabilité et de budget. Nos résultats révèlent que le problème de décision est NP-complet et que le problème d'optimisation est inapproximable, même dans le cas de préférences strictes et d'allocations de capacités disjointes. Ces résultats posent des défis importants aux décideurs qui cherchent des solutions efficaces aux problèmes urgents du monde réel. Dans la seconde étude, en utilisant le modèle du choix de l'école, nous explorons l'optimisation conjointe de l'augmentation des capacités scolaires et de la réalisation d'appariements stables optimaux pour les étudiants au sein d'un marché élargi. Nous concevons une formulation innovante de programmation mathématique qui modélise la stabilité et l'expansion des capacités, et nous développons une méthode efficace de plan de coupe pour la résoudre. Des données réelles issues du système chilien de choix d'école valident l'impact potentiel de la planification de la capacité dans des conditions de stabilité. Dans la troisième étude, nous nous penchons sur la stabilité de l'appariement dans le cadre de priorités dynamiques, en nous concentrant principalement sur le choix de l'école. Nous introduisons un modèle qui tient compte des priorités des frères et sœurs, ce qui nécessite de nouveaux concepts de stabilité. Notre recherche identifie des scénarios où des appariements stables existent, accompagnés de mécanismes en temps polynomial pour leur découverte. Cependant, dans certains cas, nous prouvons également que la recherche d'un appariement stable de cardinalité maximale est NP-difficile sous des priorités dynamiques, ce qui met en lumière les défis liés à ces problèmes d'appariement. Collectivement, cette recherche contribue à une meilleure compréhension des capacités et des priorités dynamiques dans les scénarios d'appariement stable et ouvre de nouvelles questions et de nouvelles voies pour relever les défis d'allocation complexes dans le monde réel. / This research addresses the dynamic facets in the fundamentals of the many-to-one stable matching problem. We conduct our study in the context of school choice and hospital-resident matching. In the first study, using the resident-hospital model, we investigate the computational complexity of optimizing hospital capacity variations to maximize resident outcomes, while respecting stability and budget constraints. Our findings reveal the NP-completeness of the decision problem and the inapproximability of the optimization problem, even under strict preferences and disjoint capacity allocations. These results pose significant challenges for policymakers seeking efficient solutions to pressing real-world issues. In the second study, using the school choice model, we explore the joint optimization of increasing school capacities and achieving student-optimal stable matchings within an expanded market. We devise an innovative mathematical programming formulation that models stability and capacity expansion, and we develop an effective cutting-plane method to solve it. Real-world data from the Chilean school choice system validates the potential impact of capacity planning under stability conditions. In the third study, we delve into stable matching under dynamic priorities, primarily focusing on school choice. We introduce a model that accounts for sibling priorities, necessitating novel stability concepts. Our research identifies scenarios where stable matchings exist, accompanied by polynomial-time mechanisms for their discovery. However, in some cases, we also prove the NP-hardness of finding a maximum cardinality stable matching under dynamic priorities, shedding light on challenges related to these matching problems. Collectively, this research contributes to a deeper understanding of dynamic capacities and priorities within stable matching scenarios and opens new questions and new avenues for tackling complex allocation challenges in real-world settings.

In mathematical finance, the sensitivities of option prices to various market parameters, also known as the “Greeks”, reflect the exposure to different sources of risk. Computing these is essential to predict the impact of market moves on portfolios and to hedge them adequately. This is commonly done using Monte Carlo simulations. However, obtaining accurate estimates of the Greeks can be computationally costly. Multilevel Monte Carlo offers complexity improvements over standard Monte Carlo techniques. However the idea has never been used for the computation of Greeks. In this work we answer the following questions: can multilevel Monte Carlo be useful in this setting? If so, how can we construct efficient estimators? Finally, what computational savings can we expect from these new estimators? We develop multilevel Monte Carlo estimators for the Greeks of a range of options: European options with Lipschitz payoffs (e.g. call options), European options with discontinuous payoffs (e.g. digital options), Asian options, barrier options and lookback options. Special care is taken to construct efficient estimators for non-smooth and exotic payoffs. We obtain numerical results that demonstrate the computational benefits of our algorithms. We discuss the issues of convergence of pathwise sensitivities estimators. We show rigorously that the differentiation of common discretisation schemes for Ito processes does result in satisfactory estimators of the the exact solutions’ sensitivities. We also prove that pathwise sensitivities estimators can be used under some regularity conditions to compute the Greeks of options whose underlying asset’s price is modelled as an Ito process. We present several important results on the moments of the solutions of stochastic differential equations and their discretisations as well as the principles of the so-called “extreme path analysis”. We use these to develop a rigorous analysis of the complexity of the multilevel Monte Carlo Greeks estimators constructed earlier. The resulting complexity bounds appear to be sharp and prove that our multilevel algorithms are more efficient than those derived from standard Monte Carlo.

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay / L'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, le bon fonctionnement de ces systèmes n'est assuré que lorsque leurs comportements ne dépendent pas d'un ordre d'exécution prédéterminé. En raison de cette caractéristique, il est particulièrement difficile de s'assurer qu'un système concurrent ne possède pas de faille. Dans cette thèse, nous étudions la vérification formelle, une approche algorithmique qui vise à automatiser la vérification du bon fonctionnement de systèmes concurrents en procédant par une abstraction vers des modèles mathématiques. Nous considérons deux de ces modèles, les réseaux de Petri et les systèmes d'addition de vecteurs, et les problèmes de vérification qui leur sont associés. Nous montrons que le problème d'accessibilité pour les systèmes d'addition de vecteurs (avec états) à deux compteurs est PSPACE-complet, c'est-à-dire complet pour la classe des problèmes solubles à l'aide d'une quantité polynomiale de mémoire. Nous établissons ainsi la complexité calculatoire précise de ce problème, répondant à une question demeurée ouverte depuis plus de trente ans. Nous proposons une nouvelle approche au problème de couverture pour les réseaux de Petri, basée sur un algorithme arrière guidé par une caractérisation logique de l'accessibilité dans les réseaux de Petri continus. Cette approche nous a permis de mettre au point un nouvel algorithme qui s'avère particulièrement efficace en pratique, tel que démontré par notre implémentation logicielle nommée QCover. Nous complétons ces résultats par une étude des systèmes de transitions bien structurés qui constituent une abstraction générale des systèmes d'addition de vecteurs et des réseaux de Petri. Nous considérons le cas des systèmes de transitions bien structurés à branchement infini, une classe qui inclut les réseaux de Petri possédant des arcs pouvant consommer ou produire un nombre arbitraire de jetons. Nous développons des outils mathématiques facilitant l'étude de ces systèmes et nous délimitons les frontières au-delà desquelles la décidabilité des problèmes de terminaison, de finitude, de maintenabilité et de couverture est perdue. / One fundamental aspect of computer systems, and in particular of critical systems, is the ability to run simultaneously many processes sharing resources. Such concurrent systems only work correctly when their behaviours are independent of any execution ordering. For this reason, it is particularly difficult to ensure the correctness of concurrent systems. In this thesis, we study formal verification, an algorithmic approach to the verification of concurrent systems based on mathematical modeling. We consider two of the most prominent models, Petri nets and vector addition systems, and their usual verification problems considered in the literature. We show that the reachability problem for vector addition systems (with states) restricted to two counters is PSPACE-complete, that is, it is complete for the class of problems solvable with a polynomial amount of memory. Hence, we establish the precise computational complexity of this problem, left open for more than thirty years. We develop a new approach to the coverability problem for Petri nets which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. We demonstrate the effectiveness of our approach by implementing it in a tool named QCover. We complement these results with a study of well-structured transition systems which form a general abstraction of vector addition systems and Petri nets. We consider infinitely branching well-structured transition systems, a class that includes Petri nets with special transitions that may consume or produce arbitrarily many tokens. We develop mathematical tools in order to study these systems and we delineate the decidability frontier for the termination, boundedness, maintainability and coverability problems.

Ο στόχος της παρούσας διατριβής είναι η ανάπτυξη μιας νέας κλάσης εξωτερικά εξαρτώμενων στοχαστικών συναρτησιακών μοντέλων για την αναγνώριση (identification) δυναμικών συστημάτων που παρουσιάζουν πολλαπλά σημεία λειτουργίας, τα οποία καθορίζονται από μετρήσιμη εξωτερική μεταβλητή (όπως για παράδειγμα, η θερμοκρασία, η υγρασία, κ.λ.π.). Επιπλέον, στόχος είναι η ανάπτυξη καινοτόμου μεθοδολογίας διάγνωσης (ανίχνευσης, προσδιορισμού και εκτίμησης) βλαβών σε δυναμικά συστήματα βάσει των στοχαστικών συναρτησιακών μοντέλων. Η διατριβή αρχικά πραγματεύεται την ανάπτυξη κατάλληλης μεθοδολογίας που αντιμετωπίζει τα επιμέρους προβλήματα της ανίχνευσης, του προσδιορισμού και της εκτίμησης βλαβών στη σύνθετη περίπτωση όπου η κατασκευή διεγείρεται υπό σεισμική διέγερση. Η αποτίμηση της μεθόδου αποτέλεσε και το έναυσμα για τη διαμόρφωση καινοτόμου μεθοδολογίας, η οποία βασίζεται σε μια νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών συναρτησιακών μοντέλων. Τα μοντέλα αυτά έχουν την ικανότητα να αναπαριστούν, με μεγάλη ακρίβεια, μια κατασκευή για συγκεκριμένο τύπο βλάβης και συνεχές εύρος μεγεθών, χρησιμοποιώντας μοναδική μαθηματική αναπαράσταση παραμετροποιημένη ως προς το μέγεθος της βλάβης. Επισημαίνεται ότι τέτοιου τύπου συναρτησιακά μοντέλα δεν αναφέρονται στην βιβλιογραφία. Οι πιο συγγενείς οικογένειες μοντέλων προέρχονται από τις επιστήμες της στατιστικής και της οικονομετρίας, οι οποίες όμως δεν παρουσιάζουν συναρτησιακή μορφή και δεν μπορούν να καλύψουν συνεχή εύρη τιμών. Εξαιτίας αυτού του γεγονότος στη συνέχεια της διατριβής ορίζεται η νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών Συναρτησιακών (F) μοντέλων Αυτοπαλινδρόμησης (AR) με Εξωγενή (X) είσοδο, των οποίων οι παράμετροι και η διασπορά του θορύβου είναι συναρτήσεις μετρήσιμης εξωτερικής μεταβλητής. Αυτή η συναρτησιακή εξάρτηση δίνει τη σημαντική ικανότητα στη νέα κλάση μοντέλων να μπορούν να χρησιμοποιηθούν: α) για τη δυναμική αναγνώριση συστημάτων με πολλαπλά σημεία λειτουργίας που καθορίζονται από μετρήσιμη εξωτερική μεταβλητή και, β) για την ανίχνευση, τον προσδιορισμό και την εκτίμηση βλαβών σε στοχαστικά δυναμικά συστήματα όπου η εξωτερική μεταβλητή είναι το μέγεθος της βλάβης. Επιπλέον, για τα μοντέλα αυτά αναπτύσσονται κατάλληλες μέθοδοι εκτίμησης των οποίων τα χαρακτηριστικά μελετώνται, και η αποτίμηση τους πραγματοποιείται μέσω προσομοιώσεων Monte Carlo. Στη συνέχεια ορίζεται η νέα κλάση εξωτερικά εξαρτώμενων στοχαστικών Συναρτησιακών (F) μοντέλων Αυτοπαλινδρόμησης (AR) και Κινητού Μέσου Όρου (ΜΑ) με Εξωγενή (X) είσοδο των οποίων επίσης οι παράμετροι και η διασπορά του θορύβου εκφράζονται ως συναρτήσεις μετρήσιμης εξωτερικής μεταβλητής. Τα μοντέλα FARΜΑX προσφέρουν επιπλέον ευελιξία σε σχέση με τα μοντέλα FARX εξαιτίας της εισαγωγής του πολυωνύμου ΜΑ. Για τα μοντέλα αυτά αναπτύσσονται επίσης κατάλληλες μεθοδολογίες εκτίμησης που βασίζονται στη μέγιστη πιθανοφάνεια και στην αρχή του σφάλματος πρόβλεψης. Επιπλέον, διαμορφώνονται δύο ακόμη μέθοδοι εκτίμησης που βασίζονται στην ελαχιστοποίηση του σφάλματος πρόβλεψης μέσω διαδοχικών γραμμικών σταδίων, οι οποίες παρουσιάζουν κάποια πρακτικά πλεονεκτήματα σε σχέση με τις προηγούμενες, μπορούν να συνδυαστούν με αυτές, αλλά απαιτούν την ανάπτυξη κατάλληλης άλγεβρας για τα μοντέλα FARΜΑX. Επίσης, μελετώνται ζητήματα όπως η συνέπεια και η ασυμπτωτική κατανομή της εκτιμήτριας σφάλματος πρόβλεψης. Η αποτίμηση όλων των μεθόδων εκτίμησης πραγματοποιείται μέσω προσομοιώσεων Monte Carlo. Τέλος, στα πλαίσια της παρούσας διατριβής αναπτύσσεται καινοτόμος μεθοδολογία ανίχνευσης, προσδιορισμού και εκτίμησης βλαβών σε δυναμικά συστήματα, η οποία βασίζεται στις νέες κλάσεις στοχαστικών συναρτησιακών μοντέλων των προηγούμενων κεφαλαίων. Η αποτίμηση της μεθοδολογίας πραγματοποιείται μέσω πειραματικής εφαρμογής σε διεθνές πρότυπο σκελετού αεροσκάφους υπό κλίμακα, όπου επιτυγχάνει με μεγάλη ακρίβεια, ανίχνευση, προσδιορισμό και εκτίμηση όλων των τύπων και μεγεθών βλάβης και επιπλέον ξεπερνά δυσκολίες που αντιμετωπίζουν άλλες τεχνικές της βιβλιογραφίας. / The aim of the present dissertation is the development of a new class of externally dependent stochastic functional models for the identification of dynamical systems under multiple operating conditions, which are defined by an external measurable variable (i.e. temperature, humidity, etc). The development of a novel methodology for fault diagnosis (fault detection, identification and estimation) in dynamical systems based upon the stochastic functional models is also an additional aim. The development of a proper method for fault detection, identification and estimation in structures under earthquake excitation is initially achieved. The method’s assessment was the motivation for the development of a novel methodology, which is based upon a new class of externally dependent stochastic functional models. These models are capable of accurately representing a structure for a certain type of fault in a continuous range of magnitudes by using a single mathematical representation parameterized in terms of the fault magnitude. It is noticed that such models are not referred in the literature until now. The most related families of models are found in sciences of statistics and econometrics. These models are mathematical representations without functional form and they are incapable of covering continuous ranges of values. Due to this fact, the new class of externally dependent stochastic Functional (F) AutoRegressive (AR) with eXogenous (X) excitation models, with parameters and innovations variance expressed as functions of a measurable external variable, is defined in the sequel of the dissertation. This functional dependence offers to the new class of models the important advantage of being used for: a) the identification of dynamical systems under multiple operating conditions which are defined by an external measurable variable and, b) fault detection, identification and estimation in stochastic dynamical systems where the external variable is the fault magnitude. Proper methods for FARX estimation are also developed and studied and their assessment is achieved via Monte Carlo simulations. In the following, the new class of externally dependent stochastic Functional (F) AutoRegressive (AR) Moving Average (MA) with eXogenous (X) excitation models, with parameters and innovations variance expressed as functions of a measurable external variable, is defined. The FARMAX models offer extra flexibility due to the MA part. Proper methods for FARMAX estimation, which are based upon the Maximum Likelihood and the Prediction Error principles, are also developed. Two further estimation methods are also formulated which are based upon minimization of the prediction error via successive linear stages. These methods offer some practical advantages comparing with the previous methods, they can be combined with the latter but they require the development of a proper algebra for FARMAX models. Additionally, the consistency and the asymptotic distribution of the prediction error estimator are considered. The assessment of all estimation methods is achieved via Monte Carlo simulations. In the last part of the dissertation a novel methodology for fault detection, identification and estimation in dynamical systems, which is based upon the new class of stochastic functional models of the previous chapters, is developed. The methodology’s assessment is accomplished via an experimental application in a prototype scale aircraft skeleton structure, where it achieves accurate fault detection, identification and estimation of several kinds and magnitudes of faults and also overcomes difficulties that are referred by other methods.

Attention, ce résumé comporte un peu d'ironie et d'humour. Dans ce mémoire, nous défendons l'idée selon laquelle, pour tout modèle de calcul raisonnable, ce n'est plus tant le modèle qui compte pour caractériser les classes de complexité importantes que la complexité de la structure combinatoire sous-jacente et en définitive d'un graphe sous-jacent. Pour prendre l'exemple des circuits booléens ou algébriques comme modèles, tout ce qui importe est la complexité du graphe orienté sous-jacent au circuit. Par modèle de calcul raisonnable, nous entendons, comme il se doit, un modèle qui étudié sur une classe de graphes standard nous donne la classe de complexité standard attendue afin de satisfaire aux règles élémentaires des tautologies. On pourrait aussi choisir comme modèles raisonnables les modèles Turing-complet (ou une autre notion de complétude plus adaptée selon les objets calculés), formalisables dans une logique simple (afin d'éviter les "tricheries" et les modèles conçus spécialement pour faire échouer la belle idée défendue). Néanmoins, cette seconde option n'étant pas sans risque, nous nous contentons de la proposer. La thèse défendue est une version un peu plus formalisée et précise mathématiquement de cette idée aux contours un peu flous et qui est donc nécessairement un peu fausse telle quelle.

The search for the closest lattice point arises in many communication problems, and is known to be NP-hard. The Maximum Likelihood (ML) Detector is the optimal detector which yields an optimal solution to this problem, but at the expense of high computational complexity. Existing near-optimal methods used to solve the problem are based on the Sphere Decoder (SD), which searches for lattice points confined in a hyper-sphere around the received point. The SD has emerged as a powerful means of finding the solution to the ML detection problem for MIMO systems. However the bottleneck lies in the determination of the initial radius. This thesis is concerned with the detection of transmitted wireless signals in Multiple-Input Multiple-Output (MIMO) digital communication systems as efficiently and effectively as possible. The main objective of this thesis is to design efficient ML detection algorithms for MIMO systems based on the depth-first search (DFS) algorithms whilst taking into account complexity and bit error rate performance requirements for advanced digital communication systems. The increased capacity and improved link reliability of MIMO systems without sacrificing bandwidth efficiency and transmit power will serve as the key motivation behind the study of MIMO detection schemes. The fundamental principles behind MIMO systems are explored in Chapter 2. A generic framework for linear and non-linear tree search based detection schemes is then presented Chapter 3. This paves way for different methods of improving the achievable performance-complexity trade-off for all SD-based detection algorithms. The suboptimal detection schemes, in particular the Minimum Mean Squared Error-Successive Interference Cancellation (MMSE-SIC), will also serve as pre-processing as well as comparison techniques whilst channel capacity approaching Low Density Parity Check (LDPC) codes will be employed to evaluate the performance of the proposed SD. Numerical and simulation results show that non-linear detection schemes yield better performance compared to linear detection schemes, however, at the expense of a slight increase in complexity. The first contribution in this thesis is the design of a near ML-achieving SD algorithm for MIMO digital communication systems that reduces the number of search operations within the sphere-constrained search space at reduced detection complexity in Chapter 4. In this design, the distance between the ML estimate and the received signal is used to control the lower and upper bound radii of the proposed SD to prevent NP-complete problems. The detection method is based on the DFS algorithm and the Successive Interference Cancellation (SIC). The SIC ensures that the effects of dominant signals are effectively removed. Simulation results presented in this thesis show that by employing pre-processing detection schemes, the complexity of the proposed SD can be significantly reduced, though at marginal performance penalty. The second contribution is the determination of the initial sphere radius in Chapter 5. The new initial radius proposed in this thesis is based on the variable parameter α which is commonly based on experience and is chosen to ensure that at least a lattice point exists inside the sphere with high probability. Using the variable parameter α, a new noise covariance matrix which incorporates the number of transmit antennas, the energy of the transmitted symbols and the channel matrix is defined. The new covariance matrix is then incorporated into the EMMSE model to generate an improved EMMSE estimate. The EMMSE radius is finally found by computing the distance between the sphere centre and the improved EMMSE estimate. This distance can be fine-tuned by varying the variable parameter α. The beauty of the proposed method is that it reduces the complexity of the preprocessing step of the EMMSE to that of the Zero-Forcing (ZF) detector without significant performance degradation of the SD, particularly at low Signal-to-Noise Ratios (SNR). More specifically, it will be shown through simulation results that using the EMMSE preprocessing step will substantially improve performance whenever the complexity of the tree search is fixed or upper bounded. The final contribution is the design of the LRAD-MMSE-SIC based SD detection scheme which introduces a trade-off between performance and increased computational complexity in Chapter 6. The Lenstra-Lenstra-Lovasz (LLL) algorithm will be utilised to orthogonalise the channel matrix H to a new near orthogonal channel matrix H ̅.The increased computational complexity introduced by the LLL algorithm will be significantly decreased by employing sorted QR decomposition of the transformed channel H ̅ into a unitary matrix and an upper triangular matrix which retains the property of the channel matrix. The SIC algorithm will ensure that the interference due to dominant signals will be minimised while the LDPC will effectively stop the propagation of errors within the entire system. Through simulations, it will be demonstrated that the proposed detector still approaches the ML performance while requiring much lower complexity compared to the conventional SD.

La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans cette thèse, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le cas où D est cyclique, nous introduisons une méthode motivée par des hypothèses biologiques et consistant à décomposer D en DAGs tels que les sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous étudions également dans cette thèse, l'inférence des voies de signalisation en combinant les informations sur les causes et sur les effets des événements extra-cellulaires. Nous modélisons ce problème par un problème d'orientation de graphes mixtes et nous effectuons une étude de complexité permettant d'identifier les instances faciles et celles difficiles.