<?xml version="1.0" encoding="UTF-8"?><lom xmlns="http://ltsc.ieee.org/xsd/LOM" xmlns:lomfr="http://www.lom-fr.fr/xsd/LOMFR" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://ltsc.ieee.org/xsd/LOM http://www.lom-fr.fr/xsd/lomfrv1.0/std/lomfr.xsd">
<general>
<identifier>
<catalog>Canal-U_Ocms</catalog>
<entry>35253</entry>
</identifier>
<title><string language="fre"><![CDATA[4.10. How efficient is this algorithm?]]></string></title>
<language>ENG</language>
<description>
<string language="fre"><![CDATA[We have seen the principle of an iterative algorithm in two paths for aligning and comparing two sequences of characters, here DNA sequences. And we understoodwhy the iterative version is much more efficient than the recursive version. But, how efficient is reallythis iterative algorithm? You remember that in order to measure the efficiency of algorithms, the computer scientists do not use any mean of measuring the time or any other thing. They evaluate the number of timethe main operation inside the algorithm is executed. In the caseof this Needleman and Wunsch algorithm which has been published 40 years ago, the operation which is critical is the comparisonbetween two letters of a pair of letters. It's easy, if you look at the algorithm, to find that the number of comparison is of the order of N multiplied by M with N and M being the lengths of the sequences. We say that the algorithmic complexity of this algorithm is quadratic. What does it mean? It means thatif the lengths of the sequences double, the execution time will be multiplied by four. It's easy to see. First, you have two sequences of lengths N and M. You double the length of the first sequence and you double the length of the fourth sequence since the number of comparison is the result of the multiplication of these two values, you see that of course you multiply the execution time by four.]]></string></description>
<keyword><string language="fre"><![CDATA[DNA]]></string></keyword><keyword><string language="fre"><![CDATA[Genome]]></string></keyword><keyword><string language="fre"><![CDATA[algorithm]]></string></keyword><keyword><string language="fre"><![CDATA[cell]]></string></keyword><keyword><string language="fre"><![CDATA[bioinformatics]]></string></keyword>
<lomfr:documentType>
<lomfr:source>LOMFRv1.0</lomfr:source>
<lomfr:value>image en mouvement</lomfr:value>
</lomfr:documentType>
</general><lifeCycle>
<contribute>
<role>
<source>LOMv1.0</source>
<value>author</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-07-06 18:15:31
FN:Francois RECHENMANN
N:RECHENMANN;Francois;;;
URL;TYPE=work:https://www.canal-u.tv/auteurs/rechenmann_francois
ROLE:author
NOTE: Ingénieur et Docteur-Ingénieur en informatique, François Rechenmann est chercheur au centre Inria Grenoble – Rhône-Alpes. Il y exerce ses activités à l’interface de l’informatique et des sciences du vivant en contribuant plus particulièrement au développement de méthodes et de logiciels pour l’analyse des séquences génomiques des microorganismes. Cofondateur de la société Genostar, qui propose des solutions bioinformatiques aux industries pharmaceutiques, agroalimentaires et biotechnologiques, il en est le conseiller scientifique. Très impliqué dans les actions de médiation scientifique, François Rechenmann est le responsable scientifique du site Interstices dont l’objectif est d’expliquer l’informatique en tant que domaine de recherche. 
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2015-02-05</dateTime></date>
</contribute>
</lifeCycle>
<metaMetadata>
<metadataSchema>LOMv1.0</metadataSchema>
<metadataSchema>LOMFRv1.0</metadataSchema>
</metaMetadata>
<technical>
<format>video/mp4</format>
<location><![CDATA[https://www.canal-u.tv/video/inria/4_10_how_efficient_is_this_algorithm.35253]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/4.10.how.efficient.is.this.algorithm._35253/c016fr.w4.s10.en.2.mp4]]></location>
<size>213515591</size>
<duration><duration>PT0H9M27S</duration></duration>
</technical>
<educational>
<learningResourceType>
<source>LOMv1.0</source>
<value>lecture</value>
</learningResourceType>
<context>
<source>LOMv1.0</source>
<value>licence</value>
</context>
<context>
<source>LOMv1.0</source>
<value>master</value>
</context>
</educational>
<rights>
<cost>
<source>LOMv1.0</source>
<value>no</value>
</cost>
<copyrightAndOtherRestrictions>
<source>LOMv1.0</source>
<value>no</value>
</copyrightAndOtherRestrictions>
<description>
<string language="fre"><![CDATA[Droits réservés à l'éditeur et aux auteurs. 
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.]]></string>
</description>
</rights>
<relation>
<kind>
<source>LOMv1.0</source>
<value>ispartof</value>
</kind>
<resource>
<identifier>
<catalog>URI</catalog>
<entry>https://www.canal-u.tv/producteurs/inria/cours_en_ligne/bioinformatics_genomes_and_algorithms/4.0</entry>
</identifier>
<description>
<string language="fre"><![CDATA[4. Sequences comparison]]></string>
</description>
</resource>
</relation>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre"><![CDATA[Universités Numériques Thématiques 2009 http://www.universites-numeriques.fr]]></string>
</source>
<taxon>
<id/>
<entry>
<string language="fre"/>
</entry>
</taxon>
</taxonPath>
</classification>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>570.285</id>
<entry>
<string language="fre"><![CDATA[biologie application informatique]]></string>
</entry>
</taxon>
</taxonPath>
</classification> </lom>