Mon compte

connexion

inscription

   Publicité D▼


 » 
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien

Significations et usages de Sankoff-Algorithmus

Définition

⇨ voir la définition de Wikipedia

   Publicité ▼

Wikipedia

Sankoff-Algorithmus

                   
  Eine RNA-Sekundärstruktur, d.h. eine Faltung einer RNA-Sequenz.

Der Sankoff-Algorithmus bezeichnet einen dynamischen Programmieralgorithmus, der in der Genetik verwendet wird, um simultan die drei Teilprobleme Alignment, Faltung und Phylogenie zu lösen. Er faltet und aligniert zugleich zwei Sequenzen, so dass unter einem Energie-Modell die freie Energie der Sekundärstrukturen und die Kosten der Editierungsoperationen des Alignments minimiert werden. Dazu verwendet der Algorithmus die Methode der dynamischen Programmierung. Die Laufzeit des Algorithmus ist in O(n^6) und der Speicherbedarf in O(n^4).

Inhaltsverzeichnis

  Fallunterscheidung

Die Rekurrenzen des Algorithmus implementieren grundlegend folgende Fallunterscheidung:

1. Ein Match von zwei Basen

2. Eine Insertion einer Base

3. Eine Deletion einer Base

4. Ein Match von zwei Basenpaaren.

Seien die beiden Eingabesequenzen u,v, mit m = |u|, n = |v| und 0\le i<j\le m, 0\le i'<j'\le n, dann ist die vereinfachte Grundstruktur der Rekurrenzen:

M[i,j,i',j'] = \begin{Bmatrix}
match(u_i, v_{i'}, M[i+1,j,i'+1,j']) & \\
ins(v_{i'}, M[i,j,i'+1,j']) &\\
del(u_{i}, M[i+1,j,i',j']) &\\
pmatch(u_i, u_k, v_{i'}, v_{k'}, M[i,k,i',k'], M[k,j,k',i]) & ,i\le k\le j \\
                    & , i'\le k'\le j' \\
\end{Bmatrix}

Fall 4 stellt sicher, dass bei gleichzeitiger Faltung beide Strukturen die gleiche Anzahl und Schachtelung von Hairpins bilden.

  Komplexität

Sei die Eingabe zwei Sequenzen u,v, mit n = max(|u|, |v|).

Die Laufzeit liegt in O(n^6). Für alle O(n^2) Teilwörter von u müssen alle O(n^2) Teilwörter von v und in jeder Fallunterscheidung zwei Grenzen, die jeweils in O(n) variieren, betrachtet werden.

Der Speicherbedarf ist in O(n^4), da alle Zwischenergebnisse für alle Teilwort-Kombinationen in einer Tabelle gespeichert werden.

  Varianten

Da O(n^6) Laufzeit in der Praxis problematisch ist, gibt es Varianten, die in der Fallunterscheidung nicht alle möglichen k bzw. k' betrachten, sondern beispielsweise nur die Basenpaare, die eine bestimmte Basenpaarwahrscheinlichkeit haben. So reduziert sich dann die Laufzeit auf O(n^4 c).

  Literatur

  •  David Sankoff: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. In: SIAM Journal on Applied Mathematics. 45, Nr. 5, Oktober 1985, S. 68-82.
   
               

 

Toutes les traductions de Sankoff-Algorithmus


Contenu de sensagent

  • définitions
  • synonymes
  • antonymes
  • encyclopédie

dictionnaire et traducteur pour sites web

Alexandria

Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !

Essayer ici, télécharger le code;

SensagentBox

Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.

Solution commerce électronique

Augmenter le contenu de votre site

Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.

Parcourir les produits et les annonces

Obtenir des informations en XML pour filtrer le meilleur contenu.

Indexer des images et définir des méta-données

Fixer la signification de chaque méta-donnée (multilingue).


Renseignements suite à un email de description de votre projet.

Jeux de lettres

Les jeux de lettre français sont :
○   Anagrammes
○   jokers, mots-croisés
○   Lettris
○   Boggle.

Lettris

Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.

boggle

Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer

Dictionnaire de la langue française
Principales Références

La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).

Copyright

Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.

Traduction

Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.

 

6030 visiteurs en ligne

calculé en 0,047s


Je voudrais signaler :
section :
une faute d'orthographe ou de grammaire
un contenu abusif (raciste, pornographique, diffamatoire)
une violation de copyright
une erreur
un manque
autre
merci de préciser :