On the Practical Solution of the Reversal Median Problem
Identifieur interne : 001387 ( Istex/Corpus ); précédent : 001386; suivant : 001388On the Practical Solution of the Reversal Median Problem
Auteurs : Alberto CapraraSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Abstract
Abstract: In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.
Url:
DOI: 10.1007/3-540-44696-6_19
Links to Exploration step
ISTEX:B3DF446E0D5A447E60C623DBF6991F6E0B7E4466Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Practical Solution of the Reversal Median Problem</title><author><name sortKey="Caprara, Alberto" sort="Caprara, Alberto" uniqKey="Caprara A" first="Alberto" last="Caprara">Alberto Caprara</name><affiliation><mods:affiliation>DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: acaprara@deis.unibo.it</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B3DF446E0D5A447E60C623DBF6991F6E0B7E4466</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-44696-6_19</idno><idno type="url">https://api.istex.fr/document/B3DF446E0D5A447E60C623DBF6991F6E0B7E4466/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001387</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001387</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Practical Solution of the Reversal Median Problem</title><author><name sortKey="Caprara, Alberto" sort="Caprara, Alberto" uniqKey="Caprara A" first="Alberto" last="Caprara">Alberto Caprara</name><affiliation><mods:affiliation>DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: acaprara@deis.unibo.it</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">B3DF446E0D5A447E60C623DBF6991F6E0B7E4466</idno><idno type="DOI">10.1007/3-540-44696-6_19</idno><idno type="ChapterID">19</idno><idno type="ChapterID">Chap19</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Alberto Caprara</name><affiliations><json:string>DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy</json:string><json:string>E-mail: acaprara@deis.unibo.it</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.</abstract><qualityIndicators><score>6.56</score><pdfVersion>1.3</pdfVersion><pdfPageSize>431 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>805</abstractCharCount><pdfWordCount>7405</pdfWordCount><pdfCharCount>36254</pdfCharCount><pdfPageCount>14</pdfPageCount><abstractWordCount>130</abstractWordCount></qualityIndicators><title>On the Practical Solution of the Reversal Median Problem</title><chapterId><json:string>19</json:string><json:string>Chap19</json:string></chapterId><refBibs><json:item><author><json:item><name>D,A Bader</name></json:item><json:item><name>B,M E Moret</name></json:item><json:item><name>M Yan</name></json:item></author><host><author></author><title>Proceedings of the Seventh Workshop on Algorithms and Data Structgures (WADS'01)</title><publicationDate>2001</publicationDate></host><title>A Linear-Time Algorithm for Computing Inversion Distance Between Signed Permutations with an Experimental Study</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>V Bafna</name></json:item><json:item><name>P,A Pevzner</name></json:item></author><host><volume>25</volume><pages><last>289</last><first>272</first></pages><author></author><title>Genome Rearrangements and Sorting by Reversals " , SIAM Journal on Computing</title><publicationDate>1996</publicationDate></host><publicationDate>1996</publicationDate></json:item><json:item><author><json:item><name>M Blanchette</name></json:item><json:item><name>G Bourque</name></json:item><json:item><name>D Sankoff</name></json:item></author><host><pages><last>34</last><first>25</first></pages><author></author><title>Proceedings of Genome Informatics</title><publicationDate>1997</publicationDate></host><title>Breakpoint Phylogenies</title><publicationDate>1997</publicationDate></json:item><json:item><host><author><json:item><name>M Blanchette</name></json:item></author></host></json:item><json:item><author><json:item><name>D Bryant</name></json:item></author><host><author></author><title>Journal of Discrete Algorithms</title><publicationDate>2001</publicationDate></host><title>A Lower Bound for the Breakpoint Phylogeny Problem</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>A Caprara</name></json:item></author><host><pages><last>93</last><first>84</first></pages><author></author><title>Proceedings of the Third Annual International Conference on Computational Molecular Biology (RE- COMB'99)</title><publicationDate>1999</publicationDate></host><title>Formulations and Hardness of Multiple Sorting by Reversals</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>A Caprara</name></json:item><json:item><name>G Lancia</name></json:item><json:item><name>S,K Ng</name></json:item></author><host><author></author><title>Journal on Computing</title><publicationDate>2001</publicationDate></host><title>Sorting Permutations by Reversals through Branchand-Price " , to appear in INFORMS</title><publicationDate>2001</publicationDate></json:item><json:item><host><pages><last>121</last><first>99</first></pages><author><json:item><name>M,E Cosner</name></json:item><json:item><name>R,K Jansen</name></json:item><json:item><name>B,M E Moret</name></json:item><json:item><name>L,A Rauberson</name></json:item><json:item><name>L,S Wang</name></json:item><json:item><name>T Warnow</name></json:item><json:item><name>S Wyman</name></json:item></author><title>An Empirical Comparison of Phylogenetic Methods on Chloroplast Gene Order Data in Campanulaceae</title></host></json:item><json:item><author><json:item><name>M Grötschel</name></json:item><json:item><name>L Lovász</name></json:item><json:item><name>A Schrijver</name></json:item></author><host><volume>1</volume><pages><last>197</last><first>169</first></pages><author></author><title>Combinatorica</title><publicationDate>1981</publicationDate></host><title>The Ellipsoid Method and its Consequences in Combinatorial Optimization</title><publicationDate>1981</publicationDate></json:item><json:item><author><json:item><name>D Gusfield</name></json:item></author><host><author></author><title>Algorithms on Strings, Trees and Sequences</title><publicationDate>1997</publicationDate></host><publicationDate>1997</publicationDate></json:item><json:item><author><json:item><name>S Hannenhalli</name></json:item><json:item><name>C Chappey</name></json:item><json:item><name>E,V Koonin</name></json:item><json:item><name>P,A Pevzner</name></json:item></author><host><volume>30</volume><pages><last>311</last><first>299</first></pages><author></author><title>Genomics</title><publicationDate>1995</publicationDate></host><title>Genome Sequence Comparison and Scenarios for Gene Rearrangements: A Test Case</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>S Hannenhalli</name></json:item><json:item><name>P,A Pevzner</name></json:item></author><host><volume>48</volume><pages><last>27</last><first>1</first></pages><author></author><title>Journal of the ACM</title><publicationDate>1999</publicationDate></host><title>Transforming Cabbage into Turnip (Polynomial Algorithm for Sorting Signed Permutations by Reversals)</title><publicationDate>1999</publicationDate></json:item><json:item><author><json:item><name>M Jünger</name></json:item><json:item><name>G Reinelt</name></json:item><json:item><name>G Rinaldi</name></json:item></author><host><volume>7</volume><pages><last>330</last><first>225</first></pages><author></author><title>Network Models, Handbooks in Operations Research and Management Science</title><publicationDate>1995</publicationDate></host><title>The traveling salesman problem</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>H Kaplan</name></json:item><json:item><name>R Shamir</name></json:item><json:item><name>R,E Tarjan</name></json:item></author><host><volume>29</volume><pages><last>892</last><first>880</first></pages><author></author><title>SIAM Journal on Computing</title><publicationDate>2000</publicationDate></host><title>Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals</title><publicationDate>2000</publicationDate></json:item><json:item><author><json:item><name>J Kececioglu</name></json:item><json:item><name>D Sankoff</name></json:item></author><host><pages><last>325</last><first>307</first></pages><author></author><title>Proceedings of 5th Annual Symposium on Combinatorial Pattern Matching</title><publicationDate>1994</publicationDate></host><title>Efficient Bounds for Oriented Chromosome Inversion Distance</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>J Kececioglu</name></json:item><json:item><name>D Sankoff</name></json:item></author><host><volume>13</volume><pages><last>210</last><first>180</first></pages><author></author><title>Algorithmica</title><publicationDate>1995</publicationDate></host><title>Exact and Approximation Algorithms for Sorting by Reversals , with Application to Genome Rearrangement</title><publicationDate>1995</publicationDate></json:item><json:item><host><author><json:item><name>B,M E Moret</name></json:item><json:item><name>L,S Wang</name></json:item><json:item><name>T Warnow</name></json:item><json:item><name>S,K Wyman</name></json:item></author><title>Highly accurate reconstruction of phylogenies from gene order data</title><publicationDate>2000</publicationDate></host></json:item><json:item><author><json:item><name>B,M E Moret</name></json:item><json:item><name>S,K Wyman</name></json:item><json:item><name>D,A Bader</name></json:item><json:item><name>T Warnow</name></json:item><json:item><name>M Yan</name></json:item></author><host><pages><last>594</last><first>583</first></pages><author></author><title>Proceedings of the Sixth Pacific Symposium on Biocomputing</title><publicationDate>2001</publicationDate></host><title>A New Implementation and Detailed Study of Breakpoint Analysis</title><publicationDate>2001</publicationDate></json:item><json:item><host><author></author><title>Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics</title><publicationDate>2000</publicationDate></host></json:item><json:item><author><json:item><name>R Pe 'er</name></json:item><json:item><name> Shamir</name></json:item></author><host><volume>71</volume><author></author><title>ECCC Report No</title><publicationDate>1998</publicationDate></host><title>The Median Problems for Breakpoints are N P- Complete</title><publicationDate>1998</publicationDate></json:item><json:item><host><pages><last>241</last><first>225</first></pages><author><json:item><name>I </name></json:item><json:item><name>R Shamir</name></json:item></author><title>Approximation Algorithms for the Median Problem in the Breakpoint Model</title></host></json:item><json:item><author><json:item><name>D Sankoff</name></json:item><json:item><name>M Blanchette</name></json:item></author><host><volume>5</volume><pages><last>570</last><first>555</first></pages><author></author><title>Journal of Computational Biology</title><publicationDate>2000</publicationDate></host><title>Multiple Genome Rearrangement and Breakpoint Phylogenies</title><publicationDate>2000</publicationDate></json:item><json:item><author><json:item><name>D Sankoff</name></json:item><json:item><name>D Bryant</name></json:item><json:item><name>M Denault</name></json:item><json:item><name>B,F Lang</name></json:item><json:item><name>G Burger</name></json:item></author><host><author></author><title>Journal of Computational Biology</title><publicationDate>2001</publicationDate></host><title>Early Eukaryote Evolution Based on Mitochondrial Gene Order Breakpoints</title><publicationDate>2001</publicationDate></json:item><json:item><host><pages><last>550</last><first>537</first></pages><author><json:item><name>D Sankoff</name></json:item><json:item><name>N </name></json:item></author><title>Duplication, Rearrangement and Reconciliation</title></host></json:item><json:item><author><json:item><name>D Sankoff</name></json:item><json:item><name>G Sundaram</name></json:item><json:item><name>J Kececioglu</name></json:item></author><host><volume>7</volume><pages><last>9</last><first>1</first></pages><author></author><title>International Journal of Foundations of Computer Science</title><publicationDate>1996</publicationDate></host><title>Steiner Points in the Space of Genome Rearrangements</title><publicationDate>1996</publicationDate></json:item><json:item><author><json:item><name>J Setubal</name></json:item><json:item><name>J Meidanis</name></json:item></author><host><author></author><title>Introduction to Computational Molecular Biology</title><publicationDate>1997</publicationDate></host><publicationDate>1997</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><title>Lecture Notes in Computer Science</title><copyrightDate>2001</copyrightDate></serie><host><editor><json:item><name>Olivier Gascuel</name><affiliations><json:string>LIRMM, 161 rue Ada, 34392, Montpellier, France</json:string><json:string>E-mail: gascuel@lirmm.fr</json:string></affiliations></json:item><json:item><name>Bernard M. E. Moret</name><affiliations><json:string>Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA</json:string><json:string>E-mail: moret@cs.unm.edu</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Mathematics of Computing</value></json:item><json:item><value>Computer Appl. in Life Sciences</value></json:item><json:item><value>Combinatorics</value></json:item></subject><isbn><json:string>978-3-540-42516-8</json:string></isbn><language><json:string>unknown</json:string></language><title>Algorithms in Bioinformatics</title><bookId><json:string>3-540-44696-6</json:string></bookId><volume>2149</volume><pages><last>251</last><first>238</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-44696-5</json:string></eisbn><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-44696-6</json:string></doi></host><publicationDate>2001</publicationDate><copyrightDate>2001</copyrightDate><doi><json:string>10.1007/3-540-44696-6_19</json:string></doi><id>B3DF446E0D5A447E60C623DBF6991F6E0B7E4466</id><score>0.0191863</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/B3DF446E0D5A447E60C623DBF6991F6E0B7E4466/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/B3DF446E0D5A447E60C623DBF6991F6E0B7E4466/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/B3DF446E0D5A447E60C623DBF6991F6E0B7E4466/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">On the Practical Solution of the Reversal Median Problem</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2001</p></availability><date>2001</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">On the Practical Solution of the Reversal Median Problem</title><author xml:id="author-1"><persName><forename type="first">Alberto</forename><surname>Caprara</surname></persName><email>acaprara@deis.unibo.it</email><affiliation>DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy</affiliation></author></analytic><monogr><title level="m">Algorithms in Bioinformatics</title><title level="m" type="sub">First International Workshop, WABI 2001 Århus Denmark, August 28–31, 2001 Proceedings</title><idno type="pISBN">978-3-540-42516-8</idno><idno type="eISBN">978-3-540-44696-5</idno><idno type="pISSN">0302-9743</idno><idno type="DOI">10.1007/3-540-44696-6</idno><idno type="book-ID">3-540-44696-6</idno><idno type="book-title-ID">71328</idno><idno type="book-sequence-number">2149</idno><idno type="book-volume-number">2149</idno><idno type="book-chapter-count">23</idno><editor><persName><forename type="first">Olivier</forename><surname>Gascuel</surname></persName><email>gascuel@lirmm.fr</email><affiliation>LIRMM, 161 rue Ada, 34392, Montpellier, France</affiliation></editor><editor><persName><forename type="first">Bernard</forename><forename type="first">M.</forename><forename type="first">E.</forename><surname>Moret</surname></persName><email>moret@cs.unm.edu</email><affiliation>Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2001-08-17"></date><biblScope unit="volume">2149</biblScope><biblScope unit="page" from="238">238</biblScope><biblScope unit="page" to="251">251</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2001</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="series-Id">558</idno></series><idno type="istex">B3DF446E0D5A447E60C623DBF6991F6E0B7E4466</idno><idno type="DOI">10.1007/3-540-44696-6_19</idno><idno type="ChapterID">19</idno><idno type="ChapterID">Chap19</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2001</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I15017</label><label>I16013</label><label>I17001</label><label>L17004</label><label>M17009</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Data Structures</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Mathematics of Computing</term></item><item><term>Computer Appl. in Life Sciences</term></item><item><term>Combinatorics</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2001-08-17">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/B3DF446E0D5A447E60C623DBF6991F6E0B7E4466/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" TocLevels="0"><BookID>3-540-44696-6</BookID><BookTitle>Algorithms in Bioinformatics</BookTitle><BookSubTitle>First International Workshop, WABI 2001 Århus Denmark, August 28–31, 2001 Proceedings</BookSubTitle><BookVolumeNumber>2149</BookVolumeNumber><BookSequenceNumber>2149</BookSequenceNumber><BookDOI>10.1007/3-540-44696-6</BookDOI><BookTitleID>71328</BookTitleID><BookPrintISBN>978-3-540-42516-8</BookPrintISBN><BookElectronicISBN>978-3-540-44696-5</BookElectronicISBN><BookChapterCount>23</BookChapterCount><BookHistory><OnlineDate><Year>2001</Year><Month>8</Month><Day>17</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I15017" Priority="2" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I17001" Priority="4" Type="Secondary">Mathematics of Computing</BookSubject><BookSubject Code="L17004" Priority="5" Type="Secondary">Computer Appl. in Life Sciences</BookSubject><BookSubject Code="M17009" Priority="6" Type="Secondary">Combinatorics</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Olivier</GivenName><FamilyName>Gascuel</FamilyName></EditorName><Contact><Email>gascuel@lirmm.fr</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Bernard</GivenName><GivenName>M.</GivenName><GivenName>E.</GivenName><FamilyName>Moret</FamilyName></EditorName><Contact><Email>moret@cs.unm.edu</Email></Contact></Editor><Affiliation ID="Aff4"><OrgName>LIRMM</OrgName><OrgAddress><Street>161 rue Ada</Street><Postcode>34392</Postcode><City>Montpellier</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of New Mexico</OrgName><OrgAddress><City>Albuquerque</City><State>NM</State><Postcode>87131</Postcode><Country>USA</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Chapter ID="Chap19" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>19</ChapterID><ChapterDOI>10.1007/3-540-44696-6_19</ChapterDOI><ChapterSequenceNumber>19</ChapterSequenceNumber><ChapterTitle Language="En">On the Practical Solution of the Reversal Median Problem</ChapterTitle><ChapterFirstPage>238</ChapterFirstPage><ChapterLastPage>251</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2001</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2001</Year><Month>8</Month><Day>16</Day></RegistrationDate><OnlineDate><Year>2001</Year><Month>8</Month><Day>17</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3-540-44696-6</BookID><BookTitle>Algorithms in Bioinformatics</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Alberto</GivenName><FamilyName>Caprara</FamilyName></AuthorName><Contact><Email>acaprara@deis.unibo.it</Email></Contact></Author><Affiliation ID="Aff6"><OrgDivision>DEIS</OrgDivision><OrgName>Università di Bologna</OrgName><OrgAddress><Street>Viale Risorgimento 2</Street><Postcode>40136</Postcode><City>Bologna</City><Country>Italy</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>In this paper, we study the <Emphasis Type="Italic">Reversal Median Problem</Emphasis> (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given <Emphasis Type="Italic">q</Emphasis> genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with <Emphasis Type="Italic">q</Emphasis> given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>On the Practical Solution of the Reversal Median Problem</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>On the Practical Solution of the Reversal Median Problem</title></titleInfo><name type="personal"><namePart type="given">Alberto</namePart><namePart type="family">Caprara</namePart><affiliation>DEIS, Università di Bologna, Viale Risorgimento 2, 40136, Bologna, Italy</affiliation><affiliation>E-mail: acaprara@deis.unibo.it</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2001-08-17</dateIssued><copyrightDate encoding="w3cdtf">2001</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: In this paper, we study the Reversal Median Problem (RMP), which arises in computational biology and is a basic model for the reconstruction of evolutionary trees. Given q genomes, RMP calls for another genome such that the sum of the reversal distances between this genome and the given ones is minimized. So far, the problem was considered too complex to derive mathematical models useful for its practical solution. We use the graph theoretic relaxation of RMP that we developed in a previous paper [6], essentially calling for a perfect matching in a graph that forms the maximum number of cycles jointly with q given perfect matchings, to design effective algorithms for its exact and heuristic solution. We report the solution of a few hundred instances associated with real-world genomes.</abstract><relatedItem type="host"><titleInfo><title>Algorithms in Bioinformatics</title><subTitle>First International Workshop, WABI 2001 Århus Denmark, August 28–31, 2001 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Olivier</namePart><namePart type="family">Gascuel</namePart><affiliation>LIRMM, 161 rue Ada, 34392, Montpellier, France</affiliation><affiliation>E-mail: gascuel@lirmm.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernard</namePart><namePart type="given">M.</namePart><namePart type="given">E.</namePart><namePart type="family">Moret</namePart><affiliation>Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA</affiliation><affiliation>E-mail: moret@cs.unm.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2001</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I17001">Mathematics of Computing</topic><topic authority="SpringerSubjectCodes" authorityURI="L17004">Computer Appl. in Life Sciences</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic></subject><identifier type="DOI">10.1007/3-540-44696-6</identifier><identifier type="ISBN">978-3-540-42516-8</identifier><identifier type="eISBN">978-3-540-44696-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">71328</identifier><identifier type="BookID">3-540-44696-6</identifier><identifier type="BookChapterCount">23</identifier><identifier type="BookVolumeNumber">2149</identifier><identifier type="BookSequenceNumber">2149</identifier><part><date>2001</date><detail type="volume"><number>2149</number><caption>vol.</caption></detail><extent unit="pages"><start>238</start><end>251</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2001</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></relatedItem><identifier type="istex">B3DF446E0D5A447E60C623DBF6991F6E0B7E4466</identifier><identifier type="DOI">10.1007/3-540-44696-6_19</identifier><identifier type="ChapterID">19</identifier><identifier type="ChapterID">Chap19</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2001</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001387 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001387 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:B3DF446E0D5A447E60C623DBF6991F6E0B7E4466
|texte= On the Practical Solution of the Reversal Median Problem
}}
| This area was generated with Dilib version V0.6.31. |  |