InforLorV4, Istex, Corpus, bibRecord, 001F29

YASS: enhancing the sensitivity of DNA similarity search

Identifieur interne : 001F29 ( Istex/Corpus ); précédent : 001F28; suivant : 001F30

YASS: enhancing the sensitivity of DNA similarity search

Auteurs : Laurent Noe ; Gregory Kucherov

Source :

Nucleic Acids Research [ 0305-1048 ] ; 2005-07-01.

RBID : ISTEX:8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44

English descriptors

Teeft :
- Algorithm, Alignment, Bioinformatics, Biol, Coding regions, Combinatorial pattern, Fasta format, Genomic, Homology, Homology search, Local alignment, Local alignment tool, Markov models, Nucleic, Nucleic acids, Nucleic acids research, Other parameters, Oxford university press, Preselected, Real genomic sequences, Relevant alignments, Seed pattern, Seed sensitivity, Selectivity, Server, Server issue, Similarity search, Standalone, Standalone version, Tabular, Tabular format, Target alignments, Text representation, User, Yass.

Abstract

YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (http://www.loria.fr/projects/YASS/) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.

Url:

https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/fulltext.pdf

DOI: 10.1093/nar/gki478

Links to Exploration step

ISTEX:8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">YASS: enhancing the sensitivity of DNA similarity search</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noe">Laurent Noe</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@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, 54602 Villers-les-Nancy, France</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44</idno>
<date when="2005" year="2005">2005</date>
<idno type="doi">10.1093/nar/gki478</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001F29</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001F29</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">YASS: enhancing the sensitivity of DNA similarity search</title>
<author><name sortKey="Noe, Laurent" sort="Noe, Laurent" uniqKey="Noe L" first="Laurent" last="Noe">Laurent Noe</name>
<affiliation><mods:affiliation>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@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, 54602 Villers-les-Nancy, France</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Nucleic Acids Research</title>
<title level="j" type="abbrev">Nucl. Acids Res.</title>
<idno type="ISSN">0305-1048</idno>
<idno type="eISSN">1362-4962</idno>
<imprint><publisher>Oxford University Press</publisher>
<date type="published" when="2005-07-01">2005-07-01</date>
<biblScope unit="volume">33</biblScope>
<biblScope unit="supplement">suppl_2</biblScope>
<biblScope unit="page" from="W540">W540</biblScope>
<biblScope unit="page" to="W543">W543</biblScope>
</imprint>
<idno type="ISSN">0305-1048</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0305-1048</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Alignment</term>
<term>Bioinformatics</term>
<term>Biol</term>
<term>Coding regions</term>
<term>Combinatorial pattern</term>
<term>Fasta format</term>
<term>Genomic</term>
<term>Homology</term>
<term>Homology search</term>
<term>Local alignment</term>
<term>Local alignment tool</term>
<term>Markov models</term>
<term>Nucleic</term>
<term>Nucleic acids</term>
<term>Nucleic acids research</term>
<term>Other parameters</term>
<term>Oxford university press</term>
<term>Preselected</term>
<term>Real genomic sequences</term>
<term>Relevant alignments</term>
<term>Seed pattern</term>
<term>Seed sensitivity</term>
<term>Selectivity</term>
<term>Server</term>
<term>Server issue</term>
<term>Similarity search</term>
<term>Standalone</term>
<term>Standalone version</term>
<term>Tabular</term>
<term>Tabular format</term>
<term>Target alignments</term>
<term>Text representation</term>
<term>User</term>
<term>Yass</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (http://www.loria.fr/projects/YASS/) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.</div>
</front>
</TEI>
<istex><corpusName>oup</corpusName>
<keywords><teeft><json:string>yass</json:string>
<json:string>server</json:string>
<json:string>bioinformatics</json:string>
<json:string>genomic</json:string>
<json:string>alignment</json:string>
<json:string>standalone</json:string>
<json:string>biol</json:string>
<json:string>preselected</json:string>
<json:string>tabular</json:string>
<json:string>homology</json:string>
<json:string>standalone version</json:string>
<json:string>algorithm</json:string>
<json:string>homology search</json:string>
<json:string>nucleic acids research</json:string>
<json:string>selectivity</json:string>
<json:string>nucleic</json:string>
<json:string>local alignment</json:string>
<json:string>local alignment tool</json:string>
<json:string>other parameters</json:string>
<json:string>seed sensitivity</json:string>
<json:string>seed pattern</json:string>
<json:string>target alignments</json:string>
<json:string>coding regions</json:string>
<json:string>oxford university press</json:string>
<json:string>server issue</json:string>
<json:string>tabular format</json:string>
<json:string>text representation</json:string>
<json:string>markov models</json:string>
<json:string>fasta format</json:string>
<json:string>relevant alignments</json:string>
<json:string>nucleic acids</json:string>
<json:string>real genomic sequences</json:string>
<json:string>combinatorial pattern</json:string>
<json:string>similarity search</json:string>
<json:string>user</json:string>
</teeft>
</keywords>
<author><json:item><name>Laurent Noé</name>
<affiliations><json:string>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</json:string>
<json:string>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@loria.fr</json:string>
</affiliations>
</json:item>
<json:item><name>Gregory Kucherov</name>
<affiliations><json:string>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</json:string>
</affiliations>
</json:item>
</author>
<arkIstex>ark:/67375/HXZ-ZH73K49L-S</arkIstex>
<language><json:string>eng</json:string>
</language>
<originalGenre><json:string>other</json:string>
</originalGenre>
<abstract>YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (http://www.loria.fr/projects/YASS/) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.</abstract>
<qualityIndicators><score>4.994</score>
<pdfWordCount>1938</pdfWordCount>
<pdfCharCount>12446</pdfCharCount>
<pdfVersion>1.2</pdfVersion>
<pdfPageCount>4</pdfPageCount>
<pdfPageSize>612 x 794 pts</pdfPageSize>
<refBibsNative>true</refBibsNative>
<abstractWordCount>88</abstractWordCount>
<abstractCharCount>614</abstractCharCount>
<keywordCount>0</keywordCount>
</qualityIndicators>
<title>YASS: enhancing the sensitivity of DNA similarity search</title>
<pmid><json:string>15980530</json:string>
</pmid>
<genre><json:string>other</json:string>
</genre>
<host><title>Nucleic Acids Research</title>
<language><json:string>unknown</json:string>
</language>
<issn><json:string>0305-1048</json:string>
</issn>
<eissn><json:string>1362-4962</json:string>
</eissn>
<publisherId><json:string>nar</json:string>
</publisherId>
<volume>33</volume>
<pages><first>W540</first>
<last>W543</last>
</pages>
<genre><json:string>journal</json:string>
</genre>
</host>
<namedEntities><unitex><date><json:string>2005</json:string>
</date>
<geogName></geogName>
<orgName><json:string>Ministry of Research</json:string>
<json:string>Oxford University</json:string>
</orgName>
<orgName_funder></orgName_funder>
<orgName_provider></orgName_provider>
<persName><json:string>Pierre Valois</json:string>
<json:string>In</json:string>
<json:string>The</json:string>
<json:string>Christophe Valmir</json:string>
<json:string>Marie-Pierre Etienne</json:string>
<json:string>Mikhail Roytberg</json:string>
</persName>
<placeName></placeName>
<ref_url><json:string>http://www.loria.fr/projects/YASS/</json:string>
</ref_url>
<ref_bibl></ref_bibl>
<bibl></bibl>
</unitex>
</namedEntities>
<ark><json:string>ark:/67375/HXZ-ZH73K49L-S</json:string>
</ark>
<categories><wos><json:string>science</json:string>
<json:string>biochemistry & molecular biology</json:string>
</wos>
<scienceMetrix><json:string>health sciences</json:string>
<json:string>biomedical research</json:string>
<json:string>developmental biology</json:string>
</scienceMetrix>
<scopus><json:string>1 - Life Sciences</json:string>
<json:string>2 - Biochemistry, Genetics and Molecular Biology</json:string>
<json:string>3 - Genetics</json:string>
</scopus>
<inist><json:string>sciences appliquees, technologies et medecines</json:string>
<json:string>sciences biologiques et medicales</json:string>
<json:string>sciences biologiques fondamentales et appliquees. psychologie</json:string>
<json:string>generalites</json:string>
</inist>
</categories>
<publicationDate>2005</publicationDate>
<copyrightDate>2005</copyrightDate>
<doi><json:string>10.1093/nar/gki478</json:string>
</doi>
<id>8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44</id>
<score>1</score>
<fulltext><json:item><extension>pdf</extension>
<original>true</original>
<mimetype>application/pdf</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/fulltext.pdf</uri>
</json:item>
<json:item><extension>zip</extension>
<original>false</original>
<mimetype>application/zip</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/bundle.zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">YASS: enhancing the sensitivity of DNA similarity search</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher scheme="https://publisher-list.data.istex.fr">Oxford University Press</publisher>
<availability><licence><p>© The Author 2005. Published by Oxford University Press. All rights reserved  The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions@oupjournals.org</p>
</licence>
<p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-GTWS0RDP-M">oup</p>
</availability>
<date>2005</date>
</publicationStmt>
<notesStmt><note type="other" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-7474895G-0">other</note>
<note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note>
<note>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@loria.fr</note>
</notesStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">YASS: enhancing the sensitivity of DNA similarity search</title>
<author xml:id="author-0000"><persName><forename type="first">Laurent</forename>
<surname>Noé</surname>
</persName>
<affiliation>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</affiliation>
<affiliation>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@loria.fr</affiliation>
</author>
<author xml:id="author-0001"><persName><forename type="first">Gregory</forename>
<surname>Kucherov</surname>
</persName>
<affiliation>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</affiliation>
</author>
<idno type="istex">8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44</idno>
<idno type="ark">ark:/67375/HXZ-ZH73K49L-S</idno>
<idno type="DOI">10.1093/nar/gki478</idno>
<idno type="local">gki478</idno>
</analytic>
<monogr><title level="j">Nucleic Acids Research</title>
<title level="j" type="abbrev">Nucl. Acids Res.</title>
<idno type="pISSN">0305-1048</idno>
<idno type="eISSN">1362-4962</idno>
<idno type="publisher-id">nar</idno>
<idno type="PublisherID-hwp">nar</idno>
<idno type="PublisherID-nlm-ta">Nucleic Acids Res</idno>
<imprint><publisher>Oxford University Press</publisher>
<date type="published" when="2005-07-01"></date>
<biblScope unit="volume">33</biblScope>
<biblScope unit="supplement">suppl_2</biblScope>
<biblScope unit="page" from="W540">W540</biblScope>
<biblScope unit="page" to="W543">W543</biblScope>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><creation><date>2005</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (http://www.loria.fr/projects/YASS/) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.</p>
</abstract>
</profileDesc>
<revisionDesc><change when="2005-07-01">Published</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
<json:item><extension>txt</extension>
<original>false</original>
<mimetype>text/plain</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/fulltext.txt</uri>
</json:item>
</fulltext>
<metadata><istex:metadataXml wicri:clean="corpus oup, element #text not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="US-ASCII"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//NLM//DTD Journal Publishing DTD v2.3 20070202//EN" URI="journalpublishing.dtd" name="istex:docType"></istex:docType>
<istex:document><article xml:lang="en" article-type="other">

  <front>

    <journal-meta>

      <journal-id journal-id-type="hwp">nar</journal-id>

      <journal-id journal-id-type="nlm-ta">Nucleic Acids Res</journal-id>

<journal-id journal-id-type="publisher-id">nar</journal-id>

      <journal-title>Nucleic Acids Research</journal-title>

      <abbrev-journal-title abbrev-type="publisher">Nucl. Acids Res.</abbrev-journal-title>

      <issn pub-type="ppub">0305-1048</issn>

      <issn pub-type="epub">1362-4962</issn>

      <publisher>

        <publisher-name>Oxford University Press</publisher-name>

      </publisher>

    </journal-meta>

    <article-meta>

      <article-id pub-id-type="other">gki478</article-id>

      <article-id pub-id-type="doi">10.1093/nar/gki478</article-id>

      <article-categories>

        <subj-group subj-group-type="heading">

          <subject>Article</subject>

        </subj-group>

      </article-categories>

      <title-group>

        <article-title>YASS: enhancing the sensitivity of DNA similarity search</article-title>

      </title-group>

      <contrib-group>

        <contrib contrib-type="author">

          <name>

            <surname>Noé</surname>

            <given-names>Laurent</given-names>

          </name>

          <xref rid="COR1">*</xref>

        </contrib>

        <contrib contrib-type="author">

          <name>

            <surname>Kucherov</surname>

            <given-names>Gregory</given-names>

          </name>

        </contrib>

        <aff>LORIA/INRIA-Lorraine  615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</aff>

      </contrib-group>

      <author-notes>

        <corresp id="COR1"><sup>*</sup>
To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: <ext-link xlink:href="Laurent.Noe@loria.fr" ext-link-type="email">Laurent.Noe@loria.fr</ext-link>
</corresp>

      </author-notes>

      <pub-date pub-type="ppub">

        <day>1</day>

        <month>7</month>

        <year>2005</year>

      </pub-date>

      <volume>33</volume>

      <issue>suppl_2</issue>

      <fpage>W540</fpage>

      <lpage>W543</lpage>

      <history>

        <date date-type="accepted">

          <day>15</day>

          <month>4</month>

          <year>2005</year>

        </date>

        <date date-type="received">

          <day>23</day>

          <month>3</month>

          <year>2005</year>

        </date>

      </history>

      <permissions>

        <copyright-statement>© The Author 2005. Published by Oxford University Press. All rights reserved  The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact <ext-link xlink:href="journals.permissions@oupjournals.org" ext-link-type="email">journals.permissions@oupjournals.org</ext-link>
</copyright-statement>

        <copyright-year>2005</copyright-year>

        <license license-type="open-access">

          <p></p>

        </license>

      </permissions>

      <abstract xml:lang="en">

        <p>YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (<ext-link xlink:href="http://www.loria.fr/projects/YASS/" ext-link-type="url">http://www.loria.fr/projects/YASS/</ext-link>
) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.</p>

      </abstract>

      <custom-meta-wrap>

        <custom-meta>

          <meta-name>hwp-legacy-fpage</meta-name>

          <meta-value>W540</meta-value>

        </custom-meta>

        <custom-meta>

          <meta-name>cover-date</meta-name>

          <meta-value></meta-value>

        </custom-meta>

        <custom-meta>

          <meta-name>hwp-legacy-dochead</meta-name>

          <meta-value>research-article</meta-value>

        </custom-meta>

      </custom-meta-wrap>

    </article-meta>

  </front>

  <body>

    <sec>

      <title>INTRODUCTION</title>

      <p>Modern bioinformatics relies heavily on alignment programs and motif discovery tools, and numerous comparative genomics projects need ever more precise and faster tools for comparing two or several genomic sequences with different resolutions.</p>

      <p>Except for small sequences, the exact local alignment algorithm of Smith and Waterman (<xref rid="B1">1</xref>
) is not frequently used, and most alignments are obtained using heuristic alignment tools such as FASTA (<xref rid="B2">2</xref>
), FLASH (<xref rid="B3">3</xref>
), BLAST (<xref rid="B4">4</xref>
,<xref rid="B5">5</xref>
), BLASTZ (<xref rid="B6">6</xref>
) and PatternHunter (<xref rid="B7">7</xref>
,<xref rid="B8">8</xref>
). All these methods introduce a trade-off between two competing parameters: <italic>selectivity</italic>
 (or <italic>specificity</italic>
) directly affecting the speed of the algorithm and <italic>sensitivity</italic>
 affecting its precision (i.e. the number of relevant alignments missed). Achieving a good trade-off between sensitivity and selectivity is the key issue in local alignment tools. The recently introduced <italic>spaced seeds</italic>
 technique (<xref rid="B7">7</xref>
,<xref rid="B8">8</xref>
) allows an increase in sensitivity without loss in selectivity. This innovation triggered various studies (<xref rid="B9">9</xref>
–<xref rid="B15">15</xref>
) related to the usage, design and generalizations of spaced seeds.</p>

      <p>In this note, we present YASS (Yet Another Similarity Searcher)—a new software for computing local alignments of two DNA sequences—and its web server (<ext-link xlink:href="http://yass.loria.fr/interface.php" ext-link-type="url">http://yass.loria.fr/interface.php</ext-link>
). Compared with other tools, YASS is based on two innovations. The first is a new spaced seed model called <italic>transition-constrained seeds</italic>
 that takes advantage of statistical properties of real genomic sequences. The second feature is a new statistically founded <italic>hit criterion</italic>
 that controls the formation of groups of closely located seeds that are likely to belong to the same alignment. An implementation of these improvements, reported here, provides a fast and sensitive tool for local alignment of large genomic sequences.</p>

    </sec>

    <sec>

      <title>DESCRIPTION</title>

      <sec>

        <title>Web interface</title>

        <p>The main user input (<xref rid="FIG1">Figure 1A</xref>
) consists of one or two sequences in fasta format either chosen from a predefined database or uploaded to the web server.</p>

        <p>Once sequences have been selected, the user can run the program right away with all other parameters set by default. Alternatively, the user can set other parameters such as the scoring matrix or gap penalties (preselected matrices are proposed), and specify the DNA strain to be processed (direct, complementary or both). The user can also choose to display complete alignments rather than only alignment positions.</p>

        <p>More advanced parameters are available for expert users. For example, the right choice of the seed pattern can increase the search sensitivity considerably provided that some knowledge of target alignments is available (<xref rid="B10">10</xref>
–<xref rid="B14">14</xref>
). The web interface provides a preselection of seeds including three transition-constrained seeds, one providing a good performance compromise between coding and non-coding sequences, and the other two tuned respectively for non-coding and coding regions. The accompanying Hedera program (<ext-link xlink:href="http://www.loria.fr/projects/YASS/hedera.html" ext-link-type="url">http://www.loria.fr/projects/YASS/hedera.html</ext-link>
) is also provided for advanced users in order to design new seed patterns according to different probabilistic models of alignments (<xref rid="B15">15</xref>
).</p>

        <p>Finally, the user can specify some statistical parameters of target alignments, such as the assumed substitution rate or indel rate. These parameters control the hit criterion, i.e. the rules for grouping together closely located seeds to detect similarities.</p>

        <p>Once the results are obtained, it is possible to generate a clickable dot-plot (<xref rid="FIG2">Figure 2</xref>
) where each alignment is linked to a URL with its text representation (<xref rid="FIG1">Figure 1C</xref>
). A tabular output (<xref rid="FIG1">Figure 1B</xref>
) is also available: alignments are sorted according to their <italic>E</italic>
-value and linked to their text representation. Finally, the YASS output can also be downloaded in text format for further analysis.</p>

        <sec>

          <title>Technical issues</title>

          <p>The YASS server available at <ext-link xlink:href="http://yass.loria.fr/interface.php" ext-link-type="url">http://yass.loria.fr/interface.php</ext-link>
 currently runs Apache 2.0.47 (PHP and Perl-CGI modules) on a Linux Mandrake 9.2. Dot-plots are obtained with the GD graphical library interfaced to PHP. The YASS program has been developed in C and is distributed under the Gnu General Public License.</p>

          <p>Owing to limitations of computational resources, some restrictions have been made on the web interface. For example, uploaded files are currently limited to 3 Mb, scoring systems can be chosen only among preselected ones and for each parameter a fixed range of possible values has been settled.</p>

        </sec>

      </sec>

      <sec>

        <title>Standalone version</title>

        <p>The standalone version is recommended for frequent users or those who need specific parameters to be set outside preselected values. It provides access to two other output formats, including a BLAST-like tabular format that can be used by existing postprocessing parsers. Note that YASS does not need one of the sequences to be preprocessed (<italic>formatdb</italic>
 command of BLAST), rather, it treats both sequences on the fly.</p>

      </sec>

    </sec>

    <sec>

      <title>METHODS</title>

      <p>Here we briefly outline the underlying principles of the YASS algorithm, including some novel features. For a more detailed presentation the reader is referred to (<xref rid="B16">16</xref>
) (<ext-link xlink:href="http://www.biomedcentral.com/1471-2105/5/149/" ext-link-type="url">http://www.biomedcentral.com/1471-2105/5/149/</ext-link>
).</p>

      <sec>

        <title>Seed model</title>

        <p>Seeds are specified using a seed pattern built over a three-letter alphabet #, @ and –, where # stands for a nucleotide match, – for a don't care symbol and @ for a match or a transition (mutation A↔G or C↔T). The weight of a pattern is defined as the number of # plus half the number of @. The weight is the main characteristic of seed selectivity.</p>

        <p>The advantage of transition-constrained seeds stems from the biological observation that transition mutations are relatively more frequent than transversions, in both coding and non-coding regions. Typically, biologically relevant alignments contain about the same number of transitions and transversions, whereas transitions are half as frequent in independently and identically distributed random sequences. Transition-constrained seeds increase the possible number of transitions in a hit relative to spaced seeds without the transition constraint, and this is done without loss of sensitivity or efficiency.</p>

        <p>The sensitivity of a given seed has been estimated using the algorithm of (<xref rid="B15">15</xref>
), which is a generalization of the one proposed in (<xref rid="B11">11</xref>
). Two main alignment models have been considered: a Bernoulli model (<xref rid="B13">13</xref>
) assumed to simulate alignments of non-coding DNA and a hidden Markov model (<xref rid="B10">10</xref>
) assumed to simulate alignments of coding DNA. By default, YASS currently uses the seed #@# –– ## –– # – ##@# of weight 9, which provides a good compromise in detecting similarities in both coding and non-coding sequences. The standalone version of YASS allows users to specify their own seeds. Several preselected seeds are provided by the YASS web interface.</p>

      </sec>

      <sec>

        <title>Hit criterion</title>

        <p>YASS is based on a multi-seed hit criterion that defines a hit as a group of closely located and possibly overlapping seeds. Two seeds belong to the same group if they occur within a bounded distance or, on the other hand, are located at close dot-plot diagonals. Distance threshold parameters are computed according to probabilistic sequence models taking into account substitution and indel rates, similarly to models used in (<xref rid="B17">17</xref>
). Note that seeds of a group are allowed to overlap. An additional group size parameter sets a lower bound on the total number of individual matches and transitions of the group. Using the group size results in a flexible criterion that combines a guaranteed selectivity with a good sensitivity on both short and long similarities. More details on the hit criterion can be found in (<xref rid="B16">16</xref>
).</p>

      </sec>

      <sec>

        <title>Comparative tests</title>

        <p>To validate the better performance of transition-constrained seeds compared with ordinary spaced seeds, several comparative experiments have been presented in (<xref rid="B16">16</xref>
). Transition-constrained seeds have been shown to be more sensitive with respect to some Bernoulli and hidden Markov models of alignments of coding and non-coding DNA [Tables 1 and 2 in (<xref rid="B16">16</xref>
)]. Moreover, transition-constrained seeds have been shown to be more sensitive in detecting alignments of real genomic sequences [Table 3 in (<xref rid="B16">16</xref>
)].</p>

        <p>YASS has been compared with bl2seq (NCBI BLAST 2.2.6) according to several criteria: running time, number of significant alignments found (with <italic>E</italic>
-value ≤ 10<sup>−6</sup>
) and number of significant alignments found exclusively by one program and their total length [Table 4 in (<xref rid="B16">16</xref>
)]. The results show that YASS detects more significant alignments than bl2seq, within a smaller time for large DNA sequences.</p>

      </sec>

    </sec>

    <sec>

      <title>CONCLUSIONS</title>

      <p>In this paper, we have described YASS—a new DNA local alignment tool. The proposed web interface features several output formats suitable for a <italic>coup d'oeil</italic>
 analysis as well as for a deeper analysis of alignments. An upcoming release of YASS will include multi-seed indexing strategies and an optimized processor-cache algorithm.</p>

    </sec>

    <sec>

      <title></title>

      <p>

        <fig id="FIG1" position="float">

          <label>

            <bold>Figure 1</bold>

          </label>

          <caption>

            <p>The input window (<bold>A</bold>
) allows users to control most YASS parameters, from most basic to more advanced. Results are output in tabular format (<bold>B</bold>
), with the possibility of displaying each sequence alignment (<bold>C</bold>
).</p>

          </caption>

          <graphic xlink:href="gki478f1"></graphic>

        </fig>

      </p>

      <p>

        <fig id="FIG2" position="float">

          <label>

            <bold>Figure 2</bold>

          </label>

          <caption>

            <p>Three YASS dot-plots are shown, each obtained from pairs of closely related bacterial sequences. Green segments represent alignments of forward reads and red segments correspond to alignments between the reverse complement of one sequence and the forward read of the other.</p>

          </caption>

          <graphic xlink:href="gki478f2"></graphic>

        </fig>

      </p>

    </sec>

  </body>

  <back>

    <ack>

      <p>The authors wish to thank Marie-Pierre Etienne and Pierre Valois for their help during early stages of this work, Mikhail Roytberg for his contribution to the seed design problem and Christophe Valmir for improving the YASS code. The authors have been supported by the ACI IMPBio of the French Ministry of Research. They thank the reviewers for their helpful remarks. Funding to pay the Open Access publication charges for this article was provided by CNRS.</p>

      <p><italic>Conflict of interest statement</italic>
. None declared.</p>

    </ack>

    <ref-list>

      <title>REFERENCES</title>

      <ref id="B1">

        <label>1</label>

        <citation>Smith, T. and Waterman, M. <year>1981</year>
Identification of common molecular subsequences <source>J. Mol. Biol.</source>
  <volume>147</volume>
<fpage>195</fpage>
–197</citation>

      </ref>

      <ref id="B2">

        <label>2</label>

        <citation>Lipman, D. and Pearson, W. <year>1988</year>
Improved tools for biological sequence comparison <source>Proc. Natl Acad. Sci. USA</source>
  <volume>85</volume>
<fpage>2444</fpage>
–2448</citation>

      </ref>

      <ref id="B3">

        <label>3</label>

        <citation>Califano, A. and Rigoutsos, I. <year>1993</year>
Flash: a fast look-up algorithm for string homology <source>Proc. Int. Conf. Intell. Syst. Mol. Biol.</source>
  <volume>1</volume>
<fpage>56</fpage>
–64</citation>

      </ref>

      <ref id="B4">

        <label>4</label>

        <citation>Altschul, S., Gish, W., Miller, W., Myers, E., Lipman, D. <year>1990</year>
Basic local alignment search tool <source>J. Mol. Biol.</source>
  <volume>215</volume>
<fpage>403</fpage>
–410</citation>

      </ref>

      <ref id="B5">

        <label>5</label>

        <citation>Altschul, S., Madden, T., Schäffer, A., Zhang, J., Zhang, Z., Miller, W., Lipman, D. <year>1997</year>
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs <source>Nucleic Acids Res.</source>
  <volume>25</volume>
<fpage>3389</fpage>
–3402</citation>

      </ref>

      <ref id="B6">

        <label>6</label>

        <citation>Schwartz, S., Kent, J., Smit, A., Zhang, Z., Baertsch, R., Hardison, R., Haussler, D., Miller, W. <year>2003</year>
Human-mouse alignments with BLASTZ <source>Genome Res.</source>
  <volume>13</volume>
<fpage>103</fpage>
–107</citation>

      </ref>

      <ref id="B7">

        <label>7</label>

        <citation>Ma, B., Tromp, J., Li, M. <year>2002</year>
PatternHunter: faster and more sensitive homology search <source>Bioinformatics</source>
  <volume>18</volume>
<fpage>440</fpage>
–445</citation>

      </ref>

      <ref id="B8">

        <label>8</label>

        <citation>Burkhardt, S. and Kärkkäinen, J. <year>2001</year>
Better filtering with gapped q-grams  <italic>Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM'01)</italic>
, 1–4 July, Jerusalem, Israel  Springer pp. <fpage>73</fpage>
–85 <italic>LNCS</italic>
 2089</citation>

      </ref>

      <ref id="B9">

        <label>9</label>

        <citation>Li, M., Ma, B., Kisman, D., Tromp, J. <year>2004</year>
PatternHunter II: highly sensitive and fast homology search <source>J. Bioinform. Comput. Biol.</source>
  <volume>2</volume>
<fpage>417</fpage>
–439</citation>

      </ref>

      <ref id="B10">

        <label>10</label>

        <citation>Brejova, B., Brown, D., Vinar, T. <year>2003</year>
Optimal spaced seeds for hidden Markov models, with application to homologous coding regions  <italic>Proceedings of the 14th Symposium on Combinatorial Pattern Matching</italic>
, 25–27 June, Morelia, Mexico  Springer pp. <fpage>42</fpage>
–54 <italic>LNCS</italic>
 2676</citation>

      </ref>

      <ref id="B11">

        <label>11</label>

        <citation>Buhler, J., Keich, U., Sun, Y. <year>2003</year>
Designing seeds for similarity search in genomic DNA  <italic>Proceedings of the 7th Annual International Conference on Computational Molecular Biology (RECOMB'03)</italic>
, 10–13 April, Berlin, Germany  ACM Press pp. <fpage>67</fpage>
–75</citation>

      </ref>

      <ref id="B12">

        <label>12</label>

        <citation>Choi, K.P., Zeng, F., Zhang, L. <year>2004</year>
Good spaced seeds for homology search <source>Bioinformatics</source>
  <volume>20</volume>
<fpage>1053</fpage>
–1059</citation>

      </ref>

      <ref id="B13">

        <label>13</label>

        <citation>Keich, U., Li, M., Ma, B., Tromp, J. <year>2004</year>
On spaced seeds for similarity search <source>Discrete Appl. Math.</source>
  <volume>138</volume>
<fpage>253</fpage>
–263</citation>

      </ref>

      <ref id="B14">

        <label>14</label>

        <citation>Kucherov, G., Noé, L., Ponty, Y. <year>2004</year>
Estimating seed sensitivity on homogeneous alignments  <italic>Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE2004)</italic>
, May 19–21, Taichung, Taiwan  IEEE Computer Society Press pp. <fpage>387</fpage>
–394</citation>

      </ref>

      <ref id="B15">

        <label>15</label>

        <citation>Kucherov, G., Noé, L., Roytberg, M. <year>2004</year>
A unifying framework for seed sensitivity and its application to subset seeds   Rapport de recherche INRIA RR-5374. <ext-link xlink:href="http://www.inria.fr/rrrt/rr-5374.html" ext-link-type="url">http://www.inria.fr/rrrt/rr-5374.html</ext-link>
</citation>

      </ref>

      <ref id="B16">

        <label>16</label>

        <citation>Noé, L. and Kucherov, G. <year>2004</year>
Improved hit criteria for DNA local alignment <source>BMC Bioinformatics</source>
  <volume>5</volume>
<fpage>149</fpage>
</citation>

      </ref>

      <ref id="B17">

        <label>17</label>

        <citation>Benson, G. <year>1999</year>
Tandem repeats finder: a program to analyse DNA sequences <source>Nucleic Acids Res.</source>
  <volume>27</volume>
<fpage>573</fpage>
–580</citation>

      </ref>

    </ref-list>

  </back>

</article>

</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo lang="en"><title>YASS: enhancing the sensitivity of DNA similarity search</title>
</titleInfo>
<titleInfo type="alternative" lang="en" contentType="CDATA"><title>YASS: enhancing the sensitivity of DNA similarity search</title>
</titleInfo>
<name type="personal"><namePart type="given">Laurent</namePart>
<namePart type="family">Noé</namePart>
<affiliation>LORIA/INRIA-Lorraine 615 rue du Jardin Botanique, 54602 Villers-les-Nancy, France</affiliation>
<affiliation>*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@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, 54602 Villers-les-Nancy, France</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="other" displayLabel="other" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-7474895G-0">other</genre>
<originInfo><publisher>Oxford University Press</publisher>
<dateIssued encoding="w3cdtf">2005-07-01</dateIssued>
<copyrightDate encoding="w3cdtf">2005</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="iso639-2b">eng</languageTerm>
<languageTerm type="code" authority="rfc3066">en</languageTerm>
</language>
<abstract lang="en">YASS is a DNA local alignment tool based on an efficient and sensitive filtering algorithm. It applies transition-constrained seeds to specify the most probable conserved motifs between homologous sequences, combined with a flexible hit criterion used to identify groups of seeds that are likely to exhibit significant alignments. A web interface (http://www.loria.fr/projects/YASS/) is available to upload input sequences in fasta format, query the program and visualize the results obtained in several forms (dot-plot, tabular output and others). A standalone version is available for download from the web page.</abstract>
<note type="author-notes">*To whom correspondence should be addressed. Tel: +33 3 83 59 30 11; Fax: +33 3 83 27 83 19; Email: Laurent.Noe@loria.fr</note>
<relatedItem type="host"><titleInfo><title>Nucleic Acids Research</title>
</titleInfo>
<titleInfo type="abbreviated"><title>Nucl. Acids Res.</title>
</titleInfo>
<genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre>
<identifier type="ISSN">0305-1048</identifier>
<identifier type="eISSN">1362-4962</identifier>
<identifier type="PublisherID">nar</identifier>
<identifier type="PublisherID-hwp">nar</identifier>
<identifier type="PublisherID-nlm-ta">Nucleic Acids Res</identifier>
<part><date>2005</date>
<detail type="volume"><caption>vol.</caption>
<number>33</number>
</detail>
<detail type="supplement"><number>suppl_2</number>
</detail>
<extent unit="pages"><start>W540</start>
<end>W543</end>
</extent>
</part>
</relatedItem>
<identifier type="istex">8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44</identifier>
<identifier type="DOI">10.1093/nar/gki478</identifier>
<identifier type="local">gki478</identifier>
<accessCondition type="use and reproduction" contentType="copyright">© The Author 2005. Published by Oxford University Press. All rights reserved  The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions@oupjournals.org</accessCondition>
<recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-GTWS0RDP-M">oup</recordContentSource>
<recordOrigin>© The Author 2005. Published by Oxford University Press. All rights reserved  The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions@oupjournals.org</recordOrigin>
</recordInfo>
</mods>
<json:item><extension>json</extension>
<original>false</original>
<mimetype>application/json</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/record.json</uri>
</json:item>
</metadata>
<annexes><json:item><extension>jpeg</extension>
<original>true</original>
<mimetype>image/jpeg</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/annexes.jpeg</uri>
</json:item>
<json:item><extension>gif</extension>
<original>true</original>
<mimetype>image/gif</mimetype>
<uri>https://api.istex.fr/ark:/67375/HXZ-ZH73K49L-S/annexes.gif</uri>
</json:item>
</annexes>
<serie></serie>
</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 001F29 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001F29 | 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:8703A69482BDBF55D9A64D4C3132CDB8CDA6AF44
   |texte=   YASS: enhancing the sensitivity of DNA similarity search
}}

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

YASS: enhancing the sensitivity of DNA similarity search

YASS: enhancing the sensitivity of DNA similarity search

Source :

English descriptors

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