Algorithmes approximatifs pour le reséquençage du génome humain en utilisant les séquences courtes obtenues grâce aux technologies de séquençage à capacité élevée

Traditionnellement, la variation de la génétique humaine a toujours été étudiée au niveau du polymorphisme d'un nucléotide simple (PNS). Or, il est évident que la variation de la génétique humaine va bien audelà du PNS. De nouveaux projets visant à identifier sa variation structurelle ont été lancés en utilisant les technologies de séquençage à capacité élevée. Bien que les nouvelles technologies de séquençage ne permettent d’obtenir que des lectures courtes concernant les expériences de séquençage réalisées au laboratoire de génomique de Cambridge, la recherche de différences entre un échantillon et sa référence tend à se concentrer davantage sur les variations structurelles que sur l’examen des différences sur une base unique. Les méthodes d’analyses existantes se concentrent sur la cartographie de séquences individuelles sans chercher à les confirmer grâce à d’autres séquences issues des données expérimentales. De ce fait, certains types de variations structurelles leur échappent, même si elles sont pourtant bien représentées dans l’ensemble de données. Le stage apporte une solution pour régler ce problème. La recherche sera axée sur les données obtenues grâce aux technologies de microséquençage (technologies de séquençage à molécule simple), en mettant en particulier l’accent sur la plateforme HeliScope, qui se caractérise par une longueur de lecture non uniforme et par un modèle d’erreur particulier à dominance d’insertionsdélétions. Il semble que l’intégration de ces caractéristiques avec une cartographie simultanée de multiples séquences pose un problème NP de taille. L’équipe de recherche utilisera des algorithmes spéciaux d’optimisation combinatoire qui fournissent des solutions approximatives prouvables pour la pire éventualité, afin de cerner les séquences qui se chevauchent. Le stagiaire surveillera les caractéristiques de convergence des calculs multicartes, et les prendra par défaut afin de rapporter un sousensemble de coordonnées pour les séquences multicartes de plusieurs ensembles de seuils.

Faculty Supervisor:

M. Cenk Sahinalp

Student:

Faraz Hach

Partner:

BC Cancer Agency

Discipline:

Computer science

Sector:

Life sciences

University:

Simon Fraser University