InforLorV4, Istex, Corpus, bibRecord, 003296

Finding Approximate Repetitions under Hamming Distance

Identifieur interne : 003296 ( Istex/Corpus ); précédent : 003295; suivant : 003297

Finding Approximate Repetitions under Hamming Distance

Auteurs : Roman Kolpakov ; Gregory Kucherov

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7

Abstract

Abstract: The problem of computing tandem repetitions with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nK log K + S) algorithm is proposed (S the size of the output). This improves, in particular, the bound obtained in [17].

Url:

https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/fulltext.pdf

DOI: 10.1007/3-540-44676-1_14

Links to Exploration step

ISTEX:D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Finding Approximate Repetitions under Hamming Distance</title>
<author><name sortKey="Kolpakov, Roman" sort="Kolpakov, Roman" uniqKey="Kolpakov R" first="Roman" last="Kolpakov">Roman Kolpakov</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: roman@loria.fr</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: kucherov@loria.fr</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7</idno>
<date when="2001" year="2001">2001</date>
<idno type="doi">10.1007/3-540-44676-1_14</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003296</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003296</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Finding Approximate Repetitions under Hamming Distance</title>
<author><name sortKey="Kolpakov, Roman" sort="Kolpakov, Roman" uniqKey="Kolpakov R" first="Roman" last="Kolpakov">Roman Kolpakov</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: roman@loria.fr</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: kucherov@loria.fr</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The problem of computing tandem repetitions with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nK log K + S) algorithm is proposed (S the size of the output). This improves, in particular, the bound obtained in [17].</div>
</front>
</TEI>
<istex><corpusName>springer-ebooks</corpusName>
<author><json:item><name>Roman Kolpakov</name>
<affiliations><json:string>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</json:string>
<json:string>E-mail: roman@loria.fr</json:string>
</affiliations>
</json:item>
<json:item><name>Gregory Kucherov</name>
<affiliations><json:string>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</json:string>
<json:string>E-mail: kucherov@loria.fr</json:string>
</affiliations>
</json:item>
</author>
<arkIstex>ark:/67375/HCB-JSNW4VX6-Z</arkIstex>
<language><json:string>eng</json:string>
</language>
<originalGenre><json:string>OriginalPaper</json:string>
</originalGenre>
<abstract>Abstract: The problem of computing tandem repetitions with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nK log K + S) algorithm is proposed (S the size of the output). This improves, in particular, the bound obtained in [17].</abstract>
<qualityIndicators><score>7.564</score>
<pdfWordCount>5784</pdfWordCount>
<pdfCharCount>30772</pdfCharCount>
<pdfVersion>1.3</pdfVersion>
<pdfPageCount>12</pdfPageCount>
<pdfPageSize>430 x 650 pts</pdfPageSize>
<refBibsNative>false</refBibsNative>
<abstractWordCount>47</abstractWordCount>
<abstractCharCount>277</abstractCharCount>
<keywordCount>0</keywordCount>
</qualityIndicators>
<title>Finding Approximate Repetitions under Hamming Distance</title>
<chapterId><json:string>14</json:string>
<json:string>Chap14</json:string>
</chapterId>
<genre><json:string>conference</json:string>
</genre>
<serie><title>Lecture Notes in Computer Science</title>
<language><json:string>unknown</json:string>
</language>
<copyrightDate>2001</copyrightDate>
<issn><json:string>0302-9743</json:string>
</issn>
<volume>Session 5</volume>
<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>
</serie>
<host><title>Algorithms — ESA 2001</title>
<language><json:string>unknown</json:string>
</language>
<copyrightDate>2001</copyrightDate>
<doi><json:string>10.1007/3-540-44676-1</json:string>
</doi>
<issn><json:string>0302-9743</json:string>
</issn>
<eisbn><json:string>978-3-540-44676-7</json:string>
</eisbn>
<bookId><json:string>3-540-44676-1</json:string>
</bookId>
<isbn><json:string>978-3-540-42493-2</json:string>
</isbn>
<volume>2161</volume>
<pages><first>170</first>
<last>181</last>
</pages>
<genre><json:string>book-series</json:string>
</genre>
<editor><json:item><name>Friedhelm Meyer auf der Heide</name>
<affiliations><json:string>Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, 33095, Paderborn, Germany</json:string>
<json:string>E-mail: fmadh@upb.de</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>Discrete Mathematics in Computer Science</value>
</json:item>
<json:item><value>Computation by Abstract Devices</value>
</json:item>
<json:item><value>Computer Graphics</value>
</json:item>
<json:item><value>Computer Communication Networks</value>
</json:item>
<json:item><value>Combinatorics</value>
</json:item>
</subject>
</host>
<ark><json:string>ark:/67375/HCB-JSNW4VX6-Z</json:string>
</ark>
<publicationDate>2001</publicationDate>
<copyrightDate>2001</copyrightDate>
<doi><json:string>10.1007/3-540-44676-1_14</json:string>
</doi>
<id>D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7</id>
<score>1</score>
<fulltext><json:item><extension>pdf</extension>
<original>true</original>
<mimetype>application/pdf</mimetype>
<uri>https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/fulltext.pdf</uri>
</json:item>
<json:item><extension>zip</extension>
<original>false</original>
<mimetype>application/zip</mimetype>
<uri>https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/bundle.zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Finding Approximate Repetitions under Hamming Distance</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<availability><licence>Springer-Verlag Berlin Heidelberg</licence>
</availability>
<date when="2001">2001</date>
</publicationStmt>
<notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note>
<note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Finding Approximate Repetitions under Hamming Distance</title>
<author><persName><forename type="first">Roman</forename>
<surname>Kolpakov</surname>
</persName>
<email>roman@loria.fr</email>
<affiliation><orgName type="institution">LORIA/INRIA-Lorraine</orgName>
<address><street>615, rue du Jardin Botanique</street>
<postBox>B.P.101</postBox>
<postCode>54602</postCode>
<settlement>Villers-lès-Nancy</settlement>
<country key="FR">FRANCE</country>
</address>
</affiliation>
<affiliation><orgName type="institution">French-Russian Institute for Informatics and Applied Mathematics at Moscow University</orgName>
<address><country key=""></country>
</address>
</affiliation>
</author>
<author><persName><forename type="first">Gregory</forename>
<surname>Kucherov</surname>
</persName>
<email>kucherov@loria.fr</email>
<affiliation><orgName type="institution">LORIA/INRIA-Lorraine</orgName>
<address><street>615, rue du Jardin Botanique</street>
<postBox>B.P.101</postBox>
<postCode>54602</postCode>
<settlement>Villers-lès-Nancy</settlement>
<country key="FR">FRANCE</country>
</address>
</affiliation>
</author>
<idno type="istex">D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7</idno>
<idno type="ark">ark:/67375/HCB-JSNW4VX6-Z</idno>
<idno type="DOI">10.1007/3-540-44676-1_14</idno>
</analytic>
<monogr><title level="m" type="main">Algorithms — ESA 2001</title>
<title level="m" type="sub">9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings</title>
<title level="m" type="part">Sequences</title>
<idno type="DOI">10.1007/3-540-44676-1</idno>
<idno type="book-id">3-540-44676-1</idno>
<idno type="ISBN">978-3-540-42493-2</idno>
<idno type="eISBN">978-3-540-44676-7</idno>
<idno type="chapter-id">Chap14</idno>
<idno type="part-id">Part6</idno>
<editor><persName><forename type="first">Friedhelm</forename>
<forename type="first">Meyer</forename>
<nameLink>auf der</nameLink>
<surname>Heide</surname>
</persName>
<email>fmadh@upb.de</email>
<affiliation><orgName type="department">Department of Mathematics and Computer Science and Heinz Nixdorf Institute</orgName>
<orgName type="institution">Paderborn University</orgName>
<address><postCode>33095</postCode>
<settlement>Paderborn</settlement>
<country key="DE">GERMANY</country>
</address>
</affiliation>
</editor>
<imprint><biblScope unit="vol">2161</biblScope>
<biblScope unit="page" from="170">170</biblScope>
<biblScope unit="page" to="181">181</biblScope>
<biblScope unit="chapter-count">44</biblScope>
<biblScope unit="part-chapter-count">2</biblScope>
</imprint>
</monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<editor><persName><forename type="first">Gerhard</forename>
<surname>Goos</surname>
</persName>
<affiliation><orgName type="institution">Karlsruhe University</orgName>
<address><country key="DE">GERMANY</country>
</address>
</affiliation>
</editor>
<editor><persName><forename type="first">Juris</forename>
<surname>Hartmanis</surname>
</persName>
<affiliation><orgName type="institution">Cornell University</orgName>
<address><region>NY</region>
<country key="US">UNITED STATES</country>
</address>
</affiliation>
</editor>
<editor><persName><forename type="first">Jan</forename>
<nameLink>van</nameLink>
<surname>Leeuwen</surname>
</persName>
<affiliation><orgName type="institution">Utrecht University</orgName>
<address><country key=""></country>
</address>
</affiliation>
</editor>
<idno type="pISSN">0302-9743</idno>
<idno type="seriesID">558</idno>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><abstract xml:lang="en"><head>Abstract</head>
<p>The problem of computing tandem repetitions with <hi rend="italic">K</hi>
 possible mismatches is studied. Two main definitions are considered, and for both of them an <hi rend="italic">O</hi>
(<hi rend="italic">nK</hi>
 log <hi rend="italic">K + S</hi>
) algorithm is proposed (<hi rend="italic">S</hi>
 the size of the output). This improves, in particular, the bound obtained in [17].</p>
</abstract>
<textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label>
<item><term>Computer Science</term>
</item>
</list>
</keywords>
</textClass>
<textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label>
<item><term type="Primary">Computer Science</term>
</item>
<label>I16021</label>
<item><term type="Secondary" subtype="priority-1">Algorithm Analysis and Problem Complexity</term>
</item>
<label>I17028</label>
<item><term type="Secondary" subtype="priority-2">Discrete Mathematics in Computer Science</term>
</item>
<label>I16013</label>
<item><term type="Secondary" subtype="priority-3">Computation by Abstract Devices</term>
</item>
<label>I22013</label>
<item><term type="Secondary" subtype="priority-4">Computer Graphics</term>
</item>
<label>I13022</label>
<item><term type="Secondary" subtype="priority-5">Computer Communication Networks</term>
</item>
<label>M17009</label>
<item><term type="Secondary" subtype="priority-6">Combinatorics</term>
</item>
</list>
</keywords>
</textClass>
<langUsage><language ident="EN"></language>
</langUsage>
</profileDesc>
</teiHeader>
</istex:fulltextTEI>
<json:item><extension>txt</extension>
<original>false</original>
<mimetype>text/plain</mimetype>
<uri>https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/fulltext.txt</uri>
</json:item>
</fulltext>
<metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not 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-44676-1</BookID>
<BookTitle>Algorithms — ESA 2001</BookTitle>
<BookSubTitle>9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings</BookSubTitle>
<BookVolumeNumber>2161</BookVolumeNumber>
<BookSequenceNumber>2161</BookSequenceNumber>
<BookDOI>10.1007/3-540-44676-1</BookDOI>
<BookTitleID>69451</BookTitleID>
<BookPrintISBN>978-3-540-42493-2</BookPrintISBN>
<BookElectronicISBN>978-3-540-44676-7</BookElectronicISBN>
<BookChapterCount>44</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="I17028" Priority="2" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject>
<BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject>
<BookSubject Code="I22013" Priority="4" Type="Secondary">Computer Graphics</BookSubject>
<BookSubject Code="I13022" Priority="5" Type="Secondary">Computer Communication Networks</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>Friedhelm</GivenName>
<GivenName>Meyer</GivenName>
<Particle>auf der</Particle>
<FamilyName>Heide</FamilyName>
</EditorName>
<Contact><Email>fmadh@upb.de</Email>
</Contact>
</Editor>
<Affiliation ID="Aff4"><OrgDivision>Department of Mathematics and Computer Science and Heinz Nixdorf Institute</OrgDivision>
<OrgName>Paderborn University</OrgName>
<OrgAddress><Postcode>33095</Postcode>
<City>Paderborn</City>
<Country>Germany</Country>
</OrgAddress>
</Affiliation>
</EditorGroup>
</BookHeader>
<Part ID="Part6"><PartInfo TocLevels="0"><PartID>6</PartID>
<PartNumber>Session 5</PartNumber>
<PartSequenceNumber>6</PartSequenceNumber>
<PartTitle>Sequences</PartTitle>
<PartChapterCount>2</PartChapterCount>
<PartContext><SeriesID>558</SeriesID>
<BookID>3-540-44676-1</BookID>
<BookTitle>Algorithms — ESA 2001</BookTitle>
</PartContext>
</PartInfo>
<Chapter ID="Chap14" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>14</ChapterID>
<ChapterDOI>10.1007/3-540-44676-1_14</ChapterDOI>
<ChapterSequenceNumber>14</ChapterSequenceNumber>
<ChapterTitle Language="En">Finding Approximate Repetitions under Hamming Distance</ChapterTitle>
<ChapterFirstPage>170</ChapterFirstPage>
<ChapterLastPage>181</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>
<PartID>6</PartID>
<BookID>3-540-44676-1</BookID>
<BookTitle>Algorithms — ESA 2001</BookTitle>
</ChapterContext>
</ChapterInfo>
<ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff5" PresentAffiliationID="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Roman</GivenName>
<FamilyName>Kolpakov</FamilyName>
</AuthorName>
<Contact><Email>roman@loria.fr</Email>
</Contact>
</Author>
<Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>Gregory</GivenName>
<FamilyName>Kucherov</FamilyName>
</AuthorName>
<Contact><Email>kucherov@loria.fr</Email>
</Contact>
</Author>
<Affiliation ID="Aff5"><OrgName>LORIA/INRIA-Lorraine</OrgName>
<OrgAddress><Street>615, rue du Jardin Botanique</Street>
<Postbox>B.P.101</Postbox>
<Postcode>54602</Postcode>
<City>Villers-lès-Nancy</City>
<Country>France</Country>
</OrgAddress>
</Affiliation>
<Affiliation ID="Aff6"><OrgName>French-Russian Institute for Informatics and Applied Mathematics at Moscow University</OrgName>
<OrgAddress><Country>Russia</Country>
</OrgAddress>
</Affiliation>
</AuthorGroup>
<Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading>
<Para>The problem of computing tandem repetitions with <Emphasis Type="Italic">K</Emphasis>
 possible mismatches is studied. Two main definitions are considered, and for both of them an <Emphasis Type="Italic">O</Emphasis>
(<Emphasis Type="Italic">nK</Emphasis>
 log <Emphasis Type="Italic">K + S</Emphasis>
) algorithm is proposed (<Emphasis Type="Italic">S</Emphasis>
 the size of the output). This improves, in particular, the bound obtained in [17].</Para>
</Abstract>
</ChapterHeader>
<NoBody></NoBody>
</Chapter>
</Part>
</Book>
</Series>
</Publisher>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo lang="en"><title>Finding Approximate Repetitions under Hamming Distance</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA"><title>Finding Approximate Repetitions under Hamming Distance</title>
</titleInfo>
<name type="personal"><namePart type="given">Roman</namePart>
<namePart type="family">Kolpakov</namePart>
<affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</affiliation>
<affiliation>E-mail: roman@loria.fr</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">Gregory</namePart>
<namePart type="family">Kucherov</namePart>
<affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P.101, 54602, Villers-lès-Nancy, France</affiliation>
<affiliation>E-mail: kucherov@loria.fr</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre>
<originInfo><publisher>Springer Berlin Heidelberg</publisher>
<place><placeTerm type="text">Berlin, Heidelberg</placeTerm>
</place>
<dateIssued encoding="w3cdtf">2001</dateIssued>
<copyrightDate encoding="w3cdtf">2001</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="rfc3066">en</languageTerm>
<languageTerm type="code" authority="iso639-2b">eng</languageTerm>
</language>
<abstract lang="en">Abstract: The problem of computing tandem repetitions with K possible mismatches is studied. Two main definitions are considered, and for both of them an O(nK log K + S) algorithm is proposed (S the size of the output). This improves, in particular, the bound obtained in [17].</abstract>
<relatedItem type="host"><titleInfo><title>Algorithms — ESA 2001</title>
<subTitle>9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings</subTitle>
</titleInfo>
<name type="personal"><namePart type="given">Friedhelm</namePart>
<namePart type="given">Meyer</namePart>
<namePart type="family">auf der Heide</namePart>
<affiliation>Department of Mathematics and Computer Science and Heinz Nixdorf Institute, Paderborn University, 33095, Paderborn, Germany</affiliation>
<affiliation>E-mail: fmadh@upb.de</affiliation>
<role><roleTerm type="text">editor</roleTerm>
</role>
</name>
<genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre>
<originInfo><publisher>Springer</publisher>
<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="I17028">Discrete Mathematics in Computer Science</topic>
<topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic>
<topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic>
<topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic>
<topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic>
</subject>
<identifier type="DOI">10.1007/3-540-44676-1</identifier>
<identifier type="ISBN">978-3-540-42493-2</identifier>
<identifier type="eISBN">978-3-540-44676-7</identifier>
<identifier type="ISSN">0302-9743</identifier>
<identifier type="BookTitleID">69451</identifier>
<identifier type="BookID">3-540-44676-1</identifier>
<identifier type="BookChapterCount">44</identifier>
<identifier type="BookVolumeNumber">2161</identifier>
<identifier type="BookSequenceNumber">2161</identifier>
<identifier type="PartChapterCount">2</identifier>
<part><date>2001</date>
<detail type="part"><title>Session 5: Sequences</title>
</detail>
<detail type="volume"><number>2161</number>
<caption>vol.</caption>
</detail>
<extent unit="pages"><start>170</start>
<end>181</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><publisher>Springer</publisher>
<copyrightDate encoding="w3cdtf">2001</copyrightDate>
<issuance>serial</issuance>
</originInfo>
<identifier type="ISSN">0302-9743</identifier>
<identifier type="SeriesID">558</identifier>
<part><detail type="volume"><number>Session 5</number>
<caption>vol.</caption>
</detail>
</part>
<recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin>
</recordInfo>
</relatedItem>
<identifier type="istex">D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7</identifier>
<identifier type="ark">ark:/67375/HCB-JSNW4VX6-Z</identifier>
<identifier type="DOI">10.1007/3-540-44676-1_14</identifier>
<identifier type="ChapterID">14</identifier>
<identifier type="ChapterID">Chap14</identifier>
<accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2001</accessCondition>
<recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource>
<recordOrigin>Springer-Verlag Berlin Heidelberg, 2001</recordOrigin>
</recordInfo>
</mods>
<json:item><extension>json</extension>
<original>false</original>
<mimetype>application/json</mimetype>
<uri>https://api.istex.fr/ark:/67375/HCB-JSNW4VX6-Z/record.json</uri>
</json:item>
</metadata>
</istex>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003296 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003296 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Istex
   |étape=   Corpus
   |type=    RBID
   |clé=     ISTEX:D5BB2FF843B6177D7B4D3ABBF8DAE5785B8DD7B7
   |texte=   Finding Approximate Repetitions under Hamming Distance
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Finding Approximate Repetitions under Hamming Distance

Finding Approximate Repetitions under Hamming Distance

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri