<?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>35145</entry>
</identifier>
<title><string language="fre"><![CDATA[4.6. A path is optimal if all its sub-paths are optimal]]></string></title>
<language>ENG</language>
<description>
<string language="fre"><![CDATA[A sequence alignment between two sequences is a path in a grid. So that, an optimal sequence alignmentis an optimal path in the same grid. We'll see now that a property of this optimal path provides us with scanned lines for designing an optimization algorithm. The property is the following. A path which is optimal is made up of optimal sub-paths. To prove that, we can start byproving that if a path of length L is optimal then the path of length L minus one is also optimal. This can be proved quiteeasily ad arburdum. That is, you take the hypothesis that the path of length L is optimal and you say the path oflength L minus one is not optimal. And then, you arrive at a contradiction which means that this is proved. OK. So you can also make the samereasoning with the path of length L minus two, Lminus three and so on. And so, you arrive at the conclusionthat an optimal path is made up of optimal sub-paths. And this will explain how we candesign a schema of computation of the optimal path. The trick in this algorithm is to start with the last unitary path. That is, you remember our grid, thisis the last node of the grid. N and M are the lengths of the sequences. Here is the first sequence.]]></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:14:53
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_6_a_path_is_optimal_if_all_its_sub_paths_are_optimal.35145]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/4.1.how.to.predict.gene.protein.functions.copie.copie._35145/c016fr.w4.s6.en.2.mp4]]></location>
<size>97155613</size>
<duration><duration>PT0H4M12S</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>