<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-00834143</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-01T21:29:29+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Novel definition and algorithm for chaining fragments with proportional overlaps</title>
            <author role="aut">
              <persName>
                <forename type="first">Raluca</forename>
                <surname>Uricaru</surname>
              </persName>
              <email type="md5">3c4d350fb164b0b785b2cbd0f7a9960b</email>
              <email type="domain">labri.fr</email>
              <idno type="idhal" notation="string">ruricaru</idno>
              <idno type="idhal" notation="numeric">1202</idno>
              <idno type="halauthorid" notation="string">23594-1202</idno>
              <idno type="IDREF">https://www.idref.fr/151193681</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-5730-6428</idno>
              <orgName ref="#struct-0"/>
              <affiliation ref="#struct-388224"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Alban</forename>
                <surname>Mancheron</surname>
              </persName>
              <email type="md5">ce3caf574b0e2c250ca57256ca29269e</email>
              <email type="domain">inria.fr</email>
              <idno type="idhal" notation="string">alban-mancheron</idno>
              <idno type="idhal" notation="numeric">6019</idno>
              <idno type="halauthorid" notation="string">17693-6019</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-9249-7592</idno>
              <idno type="IDREF">https://www.idref.fr/111581362</idno>
              <affiliation ref="#struct-388224"/>
            </author>
            <author role="crp">
              <persName>
                <forename type="first">Eric</forename>
                <surname>Rivals</surname>
              </persName>
              <email type="md5">2948fa0e637f8fdead28884bcc311d7f</email>
              <email type="domain">lirmm.fr</email>
              <idno type="idhal" notation="string">eric-rivals</idno>
              <idno type="idhal" notation="numeric">2002</idno>
              <idno type="halauthorid" notation="string">23559-2002</idno>
              <idno type="ORCID">https://orcid.org/0000-0003-3791-3973</idno>
              <idno type="IDREF">https://www.idref.fr/118021850</idno>
              <affiliation ref="#struct-213159"/>
              <affiliation ref="#struct-388224"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Eric</forename>
                <surname>Rivals</surname>
              </persName>
              <email type="md5">18b1a627af6df8b912fd128ee2d82dee</email>
              <email type="domain">lirmm.fr</email>
            </editor>
            <funder>ANR Cocogen: French National Research Agency (CoCoGen project) [BLAN07-1_185484].</funder>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2013-06-14 11:55:49</date>
              <date type="whenWritten">2010-11-24</date>
              <date type="whenModified">2025-03-23 03:11:31</date>
              <date type="whenReleased">2013-06-19 15:19:21</date>
              <date type="whenProduced">2011-09-07</date>
              <date type="whenEndEmbargoed">2013-06-14</date>
              <ref type="file" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-00834143v1/document">
                <date notBefore="2013-06-14"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-00834143v1/file/OverlapChaining-author-copy.pdf" id="file-834143-1096528">
                <date notBefore="2013-06-14"/>
              </ref>
              <ref type="externalLink" target="http://hal.archives-ouvertes.fr/docs/00/52/79/15/PDF/Uricaru-etal-chaining-overlap-rr-2010-1.pdf"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="113912">
                <persName>
                  <forename>Eric</forename>
                  <surname>Rivals</surname>
                </persName>
                <email type="md5">18b1a627af6df8b912fd128ee2d82dee</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-00834143</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-00834143</idno>
            <idno type="halBibtex">uricaru:lirmm-00834143</idno>
            <idno type="halRefHtml">&lt;i&gt;Journal of Computational Biology&lt;/i&gt;, 2011, 18 (9), pp.1141-1154. &lt;a target="_blank" href="https://dx.doi.org/10.1089/cmb.2011.0126"&gt;&amp;#x27E8;10.1089/cmb.2011.0126&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Journal of Computational Biology, 2011, 18 (9), pp.1141-1154. &amp;#x27E8;10.1089/cmb.2011.0126&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://about.hal.science/hal-authorisation-v1/">HAL Authorization<ref corresp="#file-834143-1096528"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="INRA">INRA - Institut national de la recherche agronomique</idno>
            <idno type="stamp" n="MAB" corresp="LIRMM">Méthodes et Algorithmes pour la Bioinformatique</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="AGREENIUM">Archive ouverte en agrobiosciences</idno>
            <idno type="stamp" n="MIPS">Mathématiques, Informatique, Physique et Systèmes</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="INRAE">Institut National de Recherche en Agriculture, Alimentation et Environnement</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Novel definition and algorithm for chaining fragments with proportional overlaps</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Raluca</forename>
                    <surname>Uricaru</surname>
                  </persName>
                  <email type="md5">3c4d350fb164b0b785b2cbd0f7a9960b</email>
                  <email type="domain">labri.fr</email>
                  <idno type="idhal" notation="string">ruricaru</idno>
                  <idno type="idhal" notation="numeric">1202</idno>
                  <idno type="halauthorid" notation="string">23594-1202</idno>
                  <idno type="IDREF">https://www.idref.fr/151193681</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-5730-6428</idno>
                  <orgName ref="#struct-0"/>
                  <affiliation ref="#struct-388224"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Alban</forename>
                    <surname>Mancheron</surname>
                  </persName>
                  <email type="md5">ce3caf574b0e2c250ca57256ca29269e</email>
                  <email type="domain">inria.fr</email>
                  <idno type="idhal" notation="string">alban-mancheron</idno>
                  <idno type="idhal" notation="numeric">6019</idno>
                  <idno type="halauthorid" notation="string">17693-6019</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-9249-7592</idno>
                  <idno type="IDREF">https://www.idref.fr/111581362</idno>
                  <affiliation ref="#struct-388224"/>
                </author>
                <author role="crp">
                  <persName>
                    <forename type="first">Eric</forename>
                    <surname>Rivals</surname>
                  </persName>
                  <email type="md5">2948fa0e637f8fdead28884bcc311d7f</email>
                  <email type="domain">lirmm.fr</email>
                  <idno type="idhal" notation="string">eric-rivals</idno>
                  <idno type="idhal" notation="numeric">2002</idno>
                  <idno type="halauthorid" notation="string">23559-2002</idno>
                  <idno type="ORCID">https://orcid.org/0000-0003-3791-3973</idno>
                  <idno type="IDREF">https://www.idref.fr/118021850</idno>
                  <affiliation ref="#struct-213159"/>
                  <affiliation ref="#struct-388224"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">12414</idno>
                <idno type="issn">1066-5277</idno>
                <idno type="eissn">1557-8666</idno>
                <title level="j">Journal of Computational Biology</title>
                <editor>Sorin Istrail and Michael Waterman</editor>
                <imprint>
                  <publisher>Mary Ann Liebert</publisher>
                  <biblScope unit="volume">18</biblScope>
                  <biblScope unit="issue">9</biblScope>
                  <biblScope unit="pp">1141-1154</biblScope>
                  <date type="datePub">2011-09-07</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1089/cmb.2011.0126</idno>
              <ref type="publisher">http://online.liebertpub.com/doi/abs/10.1089/cmb.2011.0126</ref>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">compartive genomics</term>
                <term xml:lang="en">sweep line algorithm</term>
                <term xml:lang="en">bioinformatics</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-bi">Computer Science [cs]/Bioinformatics [q-bio.QM]</classCode>
              <classCode scheme="halDomain" n="sdv.bibs">Life Sciences [q-bio]/Quantitative Methods [q-bio.QM]</classCode>
              <classCode scheme="halDomain" n="sdv.bbm.gtp">Life Sciences [q-bio]/Biochemistry, Molecular Biology/Genomics [q-bio.GN]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>Chaining fragments is a crucial step in genome alignment. Existing chaining algorithms compute a maximum weighted chain with no overlaps allowed between adjacent fragments. In practice, using local alignments as fragments, instead of MEMs, i.e. Maximal Exact Matches, generates frequent overlaps between fragments, due to combinatorial reasons and biological factors, i.e. variable tandem repeat structures that differ in number of copies between genomic sequences. In this paper, in order to raise this limitation, we formulate a novel definition of a chain, allowing overlaps proportional to the fragments lengths, and exhibit an efficient algorithm for computing such a maximum weighted chain. We tested our algorithm on a dataset composed of 694 genome pairs and accounted for significant improvements in terms of coverage, while keeping the running times below reasonable limits. Moreover, experiments with different ratios of allowed overlaps showed the robustness of the chains with respect to these ratios.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-388224" status="OLD">
          <orgName>Méthodes et Algorithmes pour la Bioinformatique</orgName>
          <orgName type="acronym">MAB</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/MAB/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-181" type="direct"/>
            <relation name="UMR5506" active="#struct-410122" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-213159" status="OLD">
          <orgName>Institut de Biologie Computationnelle</orgName>
          <orgName type="acronym">IBC</orgName>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <addrLine>95 rue de la Galéra, 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.ibc-montpellier.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-92114" type="direct"/>
            <relation active="#struct-300009" type="direct"/>
            <relation active="#struct-410122" type="direct"/>
            <relation active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-181" status="OLD">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">1995-01-01</date>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation name="UMR5506" active="#struct-410122" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-410122" status="OLD">
          <idno type="ISNI">0000000120970141</idno>
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="end">2021-12-31</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-92114" status="OLD">
          <idno type="ROR">https://ror.org/01x3gbx83</idno>
          <orgName>Institut National de la Recherche Agronomique</orgName>
          <orgName type="acronym">INRA</orgName>
          <date type="start">1946-05-18</date>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inra.fr</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
          <orgName type="acronym">Inria</orgName>
          <desc>
            <address>
              <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>