Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment
Identifieur interne : 000156 ( Istex/Corpus ); précédent : 000155; suivant : 000157Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment
Auteurs : Yinglei Song ; Chunmei Liu ; Xiuzhen Huang ; Russell L. Malmberg ; Ying Xu ; Liming CaiSource :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k t N 2) for the structure of N residues and its tree decomposition of width t. The parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.
Url:
DOI: 10.1007/11557067_31
Links to Exploration step
ISTEX:F6316235B91C7ECC5DF547655E0F3533F36E03B0Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title><author><name sortKey="Song, Yinglei" sort="Song, Yinglei" uniqKey="Song Y" first="Yinglei" last="Song">Yinglei Song</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: cai@cs.uga.edu</mods:affiliation></affiliation></author><author><name sortKey="Liu, Chunmei" sort="Liu, Chunmei" uniqKey="Liu C" first="Chunmei" last="Liu">Chunmei Liu</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Huang, Xiuzhen" sort="Huang, Xiuzhen" uniqKey="Huang X" first="Xiuzhen" last="Huang">Xiuzhen Huang</name><affiliation><mods:affiliation>Dept. of Computer Science, Arkansas State Univ., State University, 72467, AR, USA</mods:affiliation></affiliation></author><author><name sortKey="Malmberg, Russell L" sort="Malmberg, Russell L" uniqKey="Malmberg R" first="Russell L." last="Malmberg">Russell L. Malmberg</name><affiliation><mods:affiliation>Dept. of Plant Biology, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Xu, Ying" sort="Xu, Ying" uniqKey="Xu Y" first="Ying" last="Xu">Ying Xu</name><affiliation><mods:affiliation>Dept. of Biochemistry and Molecular Biology, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Cai, Liming" sort="Cai, Liming" uniqKey="Cai L" first="Liming" last="Cai">Liming Cai</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F6316235B91C7ECC5DF547655E0F3533F36E03B0</idno><date when="2005" year="2005">2005</date><idno type="doi">10.1007/11557067_31</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-KDXGGF10-K/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000156</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000156</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title><author><name sortKey="Song, Yinglei" sort="Song, Yinglei" uniqKey="Song Y" first="Yinglei" last="Song">Yinglei Song</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: cai@cs.uga.edu</mods:affiliation></affiliation></author><author><name sortKey="Liu, Chunmei" sort="Liu, Chunmei" uniqKey="Liu C" first="Chunmei" last="Liu">Chunmei Liu</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Huang, Xiuzhen" sort="Huang, Xiuzhen" uniqKey="Huang X" first="Xiuzhen" last="Huang">Xiuzhen Huang</name><affiliation><mods:affiliation>Dept. of Computer Science, Arkansas State Univ., State University, 72467, AR, USA</mods:affiliation></affiliation></author><author><name sortKey="Malmberg, Russell L" sort="Malmberg, Russell L" uniqKey="Malmberg R" first="Russell L." last="Malmberg">Russell L. Malmberg</name><affiliation><mods:affiliation>Dept. of Plant Biology, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Xu, Ying" sort="Xu, Ying" uniqKey="Xu Y" first="Ying" last="Xu">Ying Xu</name><affiliation><mods:affiliation>Dept. of Biochemistry and Molecular Biology, Univ. of Georgia, 30602, Athens, GA, USA</mods:affiliation></affiliation></author><author><name sortKey="Cai, Liming" sort="Cai, Liming" uniqKey="Cai L" first="Liming" last="Cai">Liming Cai</name><affiliation><mods:affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</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="eISSN">1611-3349</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: Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k t N 2) for the structure of N residues and its tree decomposition of width t. The parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.</div></front></TEI><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Yinglei Song</name><affiliations><json:string>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</json:string><json:string>E-mail: cai@cs.uga.edu</json:string></affiliations></json:item><json:item><name>Chunmei Liu</name><affiliations><json:string>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</json:string></affiliations></json:item><json:item><name>Xiuzhen Huang</name><affiliations><json:string>Dept. of Computer Science, Arkansas State Univ., State University, 72467, AR, USA</json:string></affiliations></json:item><json:item><name>Russell L. Malmberg</name><affiliations><json:string>Dept. of Plant Biology, Univ. of Georgia, 30602, Athens, GA, USA</json:string></affiliations></json:item><json:item><name>Ying Xu</name><affiliations><json:string>Dept. of Biochemistry and Molecular Biology, Univ. of Georgia, 30602, Athens, GA, USA</json:string></affiliations></json:item><json:item><name>Liming Cai</name><affiliations><json:string>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-KDXGGF10-K</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>proceedings</json:string></originalGenre><abstract>Abstract: Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k t N 2) for the structure of N residues and its tree decomposition of width t. The parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.</abstract><qualityIndicators><score>9.448</score><pdfWordCount>5669</pdfWordCount><pdfCharCount>30927</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>13</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>204</abstractWordCount><abstractCharCount>1364</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title><chapterId><json:string>31</json:string><json:string>Chap31</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>2005</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>David Hutchison</name><affiliations><json:string>Lancaster University, UK</json:string></affiliations></json:item><json:item><name>Takeo Kanade</name><affiliations><json:string>Carnegie Mellon University, Pittsburgh, PA, USA</json:string></affiliations></json:item><json:item><name>Josef Kittler</name><affiliations><json:string>University of Surrey, Guildford, UK</json:string></affiliations></json:item><json:item><name>Jon M. Kleinberg</name><affiliations><json:string>Cornell University, Ithaca, NY, USA</json:string></affiliations></json:item><json:item><name>Friedemann Mattern</name><affiliations><json:string>ETH Zurich, Switzerland</json:string></affiliations></json:item><json:item><name>John C. Mitchell</name><affiliations><json:string>Stanford University, CA, USA</json:string></affiliations></json:item><json:item><name>Moni Naor</name><affiliations><json:string>Weizmann Institute of Science, Rehovot, Israel</json:string></affiliations></json:item><json:item><name>Oscar Nierstrasz</name><affiliations><json:string>University of Bern, Switzerland</json:string></affiliations></json:item><json:item><name>C. Pandu Rangan</name><affiliations><json:string>Indian Institute of Technology, Madras, India</json:string></affiliations></json:item><json:item><name>Bernhard Steffen</name><affiliations><json:string>University of Dortmund, Germany</json:string></affiliations></json:item><json:item><name>Madhu Sudan</name><affiliations><json:string>Massachusetts Institute of Technology, MA, USA</json:string></affiliations></json:item><json:item><name>Demetri Terzopoulos</name><affiliations><json:string>New York University, NY, USA</json:string></affiliations></json:item><json:item><name>Dough Tygar</name><affiliations><json:string>University of California, Berkeley, CA, USA</json:string></affiliations></json:item><json:item><name>Moshe Y. Vardi</name><affiliations><json:string>Rice University, Houston, TX, USA</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max-Planck Institute of Computer Science, Saarbruecken, Germany</json:string></affiliations></json:item></editor></serie><host><title>Algorithms in Bioinformatics</title><language><json:string>unknown</json:string></language><copyrightDate>2005</copyrightDate><doi><json:string>10.1007/11557067</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-31812-5</json:string></eisbn><bookId><json:string>978-3-540-31812-5</json:string></bookId><isbn><json:string>978-3-540-29008-7</json:string></isbn><volume>3692</volume><pages><first>376</first><last>388</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Rita Casadio</name><affiliations><json:string>Biocomputing Group, University of Bologna, Italy</json:string><json:string>E-mail: casadio@alma.unibo.it</json:string></affiliations></json:item><json:item><name>Gene Myers</name><affiliations><json:string>Janelia Farm Research Campus, Howard Hughes Medical Institute, Ashburn, Virginia, USA</json:string><json:string>E-mail: myersg@janelia.hhmi.org</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Probability and Statistics in Computer Science</value></json:item><json:item><value>Bioinformatics</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-KDXGGF10-K</json:string></ark><publicationDate>2005</publicationDate><copyrightDate>2005</copyrightDate><doi><json:string>10.1007/11557067_31</json:string></doi><id>F6316235B91C7ECC5DF547655E0F3533F36E03B0</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-KDXGGF10-K/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-KDXGGF10-K/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-KDXGGF10-K/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="2005">2005</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">Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title><author><persName><forename type="first">Yinglei</forename><surname>Song</surname></persName><email>cai@cs.uga.edu</email><affiliation><orgName type="department">Dept. of Computer Science</orgName><orgName type="institution">Univ. of Georgia</orgName><address><settlement>Athens</settlement><region>GA</region><postCode>30602</postCode><country key="US">UNITED STATES</country></address></affiliation></author><author><persName><forename type="first">Chunmei</forename><surname>Liu</surname></persName><affiliation><orgName type="department">Dept. of Computer Science</orgName><orgName type="institution">Univ. of Georgia</orgName><address><settlement>Athens</settlement><region>GA</region><postCode>30602</postCode><country key="US">UNITED STATES</country></address></affiliation></author><author><persName><forename type="first">Xiuzhen</forename><surname>Huang</surname></persName><affiliation><orgName type="department">Dept. of Computer Science</orgName><orgName type="institution">Arkansas State Univ., State University</orgName><address><region>AR</region><postCode>72467</postCode><country key="US">UNITED STATES</country></address></affiliation></author><author><persName><forename type="first">Russell</forename><forename type="first">L.</forename><surname>Malmberg</surname></persName><affiliation><orgName type="department">Dept. of Plant Biology</orgName><orgName type="institution">Univ. of Georgia</orgName><address><settlement>Athens</settlement><region>GA</region><postCode>30602</postCode><country key="US">UNITED STATES</country></address></affiliation></author><author><persName><forename type="first">Ying</forename><surname>Xu</surname></persName><affiliation><orgName type="department">Dept. of Biochemistry and Molecular Biology</orgName><orgName type="institution">Univ. of Georgia</orgName><address><settlement>Athens</settlement><region>GA</region><postCode>30602</postCode><country key="US">UNITED STATES</country></address></affiliation></author><author><persName><forename type="first">Liming</forename><surname>Cai</surname></persName><affiliation><orgName type="department">Dept. of Computer Science</orgName><orgName type="institution">Univ. of Georgia</orgName><address><settlement>Athens</settlement><region>GA</region><postCode>30602</postCode><country key="US">UNITED STATES</country></address></affiliation></author><idno type="istex">F6316235B91C7ECC5DF547655E0F3533F36E03B0</idno><idno type="ark">ark:/67375/HCB-KDXGGF10-K</idno><idno type="DOI">10.1007/11557067_31</idno></analytic><monogr><title level="m" type="main">Algorithms in Bioinformatics</title><title level="m" type="sub">5th International Workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005. Proceedings</title><title level="m" type="part">Structure</title><idno type="DOI">10.1007/11557067</idno><idno type="book-id">978-3-540-31812-5</idno><idno type="ISBN">978-3-540-29008-7</idno><idno type="eISBN">978-3-540-31812-5</idno><idno type="chapter-id">Chap31</idno><idno type="part-id">Part6</idno><editor><persName><forename type="first">Rita</forename><surname>Casadio</surname></persName><email>casadio@alma.unibo.it</email><affiliation><orgName type="department">Biocomputing Group</orgName><orgName type="institution">University of Bologna</orgName><address><country key="IT">ITALY</country></address></affiliation></editor><editor><persName><forename type="first">Gene</forename><surname>Myers</surname></persName><email>myersg@janelia.hhmi.org</email><affiliation><orgName type="institution">Janelia Farm Research Campus, Howard Hughes Medical Institute</orgName><address><settlement>Ashburn</settlement><region>Virginia</region><country key="US">UNITED STATES</country></address></affiliation></editor><imprint><biblScope unit="vol">3692</biblScope><biblScope unit="page" from="376">376</biblScope><biblScope unit="page" to="388">388</biblScope><biblScope unit="chapter-count">35</biblScope><biblScope unit="part-chapter-count">6</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation><orgName type="institution">Lancaster University</orgName><address><country key="GB">UNITED KINGDOM</country></address></affiliation></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation><orgName type="institution">Carnegie Mellon University</orgName><address><settlement>Pittsburgh</settlement><region>PA</region><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation><orgName type="institution">University of Surrey</orgName><address><settlement>Guildford</settlement><country key="GB">UNITED KINGDOM</country></address></affiliation></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation><orgName type="institution">Cornell University</orgName><address><settlement>Ithaca</settlement><region>NY</region><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation><orgName type="institution">ETH Zurich</orgName><address><country key="CH">SWITZERLAND</country></address></affiliation></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation><orgName type="institution">Stanford University</orgName><address><settlement>CA</settlement><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation><orgName type="institution">Weizmann Institute of Science</orgName><address><settlement>Rehovot</settlement><country key="IL">ISRAEL</country></address></affiliation></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation><orgName type="institution">University of Bern</orgName><address><country key="CH">SWITZERLAND</country></address></affiliation></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation><orgName type="institution">Indian Institute of Technology</orgName><address><settlement>Madras</settlement><country key="IN">INDIA</country></address></affiliation></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation><orgName type="institution">University of Dortmund</orgName><address><country key="DE">GERMANY</country></address></affiliation></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation><orgName type="institution">Massachusetts Institute of Technology</orgName><address><settlement>MA</settlement><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation><orgName type="institution">New York University</orgName><address><settlement>NY</settlement><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Dough</forename><surname>Tygar</surname></persName><affiliation><orgName type="institution">University of California</orgName><address><settlement>Berkeley</settlement><region>CA</region><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation><orgName type="institution">Rice University</orgName><address><settlement>Houston</settlement><region>TX</region><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation><orgName type="institution">Max-Planck Institute of Computer Science</orgName><address><settlement>Saarbruecken</settlement><country key="DE">GERMANY</country></address></affiliation></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases.</p><p>This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity <hi rend="italic">O</hi>(<hi rend="italic">k</hi><hi rend="superscript"><hi rend="italic">t</hi></hi><hi rend="italic">N</hi><hi rend="superscript">2</hi>) for the structure of <hi rend="italic">N</hi> residues and its tree decomposition of width <hi rend="italic">t</hi>. The parameter <hi rend="italic">k</hi>, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.</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>I15017</label><item><term type="Secondary" subtype="priority-2">Data Structures</term></item><label>I16013</label><item><term type="Secondary" subtype="priority-3">Computation by Abstract Devices</term></item><label>I17028</label><item><term type="Secondary" subtype="priority-4">Discrete Mathematics in Computer Science</term></item><label>I17036</label><item><term type="Secondary" subtype="priority-5">Probability and Statistics in Computer Science</term></item><label>L15001</label><item><term type="Secondary" subtype="priority-6">Bioinformatics</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-KDXGGF10-K/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><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff11"><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff12"><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff13"><EditorName DisplayOrder="Western"><GivenName>Dough</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff14"><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff15"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Lancaster University</OrgName><OrgAddress><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Surrey</OrgName><OrgAddress><City>Guildford</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Cornell University</OrgName><OrgAddress><City>Ithaca</City><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>ETH Zurich</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Stanford University</OrgName><OrgAddress><City>CA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgName>Weizmann Institute of Science</OrgName><OrgAddress><City>Rehovot</City><Country>Israel</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>University of Bern</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>Indian Institute of Technology</OrgName><OrgAddress><City>Madras</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgName>University of Dortmund</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff11"><OrgName>Massachusetts Institute of Technology</OrgName><OrgAddress><City>MA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff12"><OrgName>New York University</OrgName><OrgAddress><City>NY</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff13"><OrgName>University of California</OrgName><OrgAddress><City>Berkeley</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff14"><OrgName>Rice University</OrgName><OrgAddress><City>Houston</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff15"><OrgName>Max-Planck Institute of Computer Science</OrgName><OrgAddress><City>Saarbruecken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><SubSeries><SubSeriesInfo><SubSeriesID>5381</SubSeriesID><SubSeriesPrintISSN>0302-9743</SubSeriesPrintISSN><SubSeriesElectronicISSN>1611-3349</SubSeriesElectronicISSN><SubSeriesTitle Language="En">Lecture Notes in Bioinformatics</SubSeriesTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor AffiliationIDS="Aff16"><EditorName DisplayOrder="Western"><GivenName>Sorin</GivenName><FamilyName>Istrail</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff17"><EditorName DisplayOrder="Western"><GivenName>Pavel</GivenName><FamilyName>Pevzner</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff18"><EditorName DisplayOrder="Western"><GivenName>Michael</GivenName><FamilyName>Waterman</FamilyName></EditorName></Editor><Affiliation ID="Aff16"><OrgName>Celera Genomics, Applied Biosystems</OrgName><OrgAddress><City>Rockville</City><State>MD</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff17"><OrgName>University of California</OrgName><OrgAddress><City>San Diego</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff18"><OrgName>University of Southern California</OrgName><OrgAddress><City>Los Angeles</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation></EditorGroup></SubSeriesHeader></SubSeries><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-31812-5</BookID><BookTitle>Algorithms in Bioinformatics</BookTitle><BookSubTitle>5th International Workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005. Proceedings</BookSubTitle><BookVolumeNumber>3692</BookVolumeNumber><BookSequenceNumber>3692</BookSequenceNumber><BookDOI>10.1007/11557067</BookDOI><BookTitleID>126627</BookTitleID><BookPrintISBN>978-3-540-29008-7</BookPrintISBN><BookElectronicISBN>978-3-540-31812-5</BookElectronicISBN><BookChapterCount>35</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2005</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I15017" Priority="2" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I17028" Priority="4" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I17036" Priority="5" Type="Secondary">Probability and Statistics in Computer Science</BookSubject><BookSubject Code="L15001" Priority="6" Type="Secondary">Bioinformatics</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID><SubSeriesID>5381</SubSeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff19"><EditorName DisplayOrder="Western"><GivenName>Rita</GivenName><FamilyName>Casadio</FamilyName></EditorName><Contact><Email>casadio@alma.unibo.it</Email></Contact></Editor><Editor AffiliationIDS="Aff20"><EditorName DisplayOrder="Western"><GivenName>Gene</GivenName><FamilyName>Myers</FamilyName></EditorName><Contact><Email>myersg@janelia.hhmi.org</Email></Contact></Editor><Affiliation ID="Aff19"><OrgDivision>Biocomputing Group</OrgDivision><OrgName>University of Bologna</OrgName><OrgAddress><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff20"><OrgName>Janelia Farm Research Campus, Howard Hughes Medical Institute</OrgName><OrgAddress><City>Ashburn</City><State>Virginia</State><Country>USA</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part6"><PartInfo TocLevels="0"><PartID>6</PartID><PartSequenceNumber>6</PartSequenceNumber><PartTitle>Structure</PartTitle><PartChapterCount>6</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Algorithms in Bioinformatics</BookTitle></PartContext></PartInfo><SubPart ID="SubPart11"><SubPartInfo><SubPartID>11</SubPartID><SubPartNumber>1.</SubPartNumber><SubPartSequenceNumber>11</SubPartSequenceNumber><SubPartTitle>Threading</SubPartTitle><SubPartChapterCount>2</SubPartChapterCount></SubPartInfo><Chapter ID="Chap31" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>31</ChapterID><ChapterDOI>10.1007/11557067_31</ChapterDOI><ChapterSequenceNumber>31</ChapterSequenceNumber><ChapterTitle Language="En">Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</ChapterTitle><ChapterFirstPage>376</ChapterFirstPage><ChapterLastPage>388</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2005</CopyrightYear></ChapterCopyright><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>978-3-540-31812-5</BookID><BookTitle>Algorithms in Bioinformatics</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff21"><AuthorName DisplayOrder="Western"><GivenName>Yinglei</GivenName><FamilyName>Song</FamilyName></AuthorName><Contact><Email>cai@cs.uga.edu</Email></Contact></Author><Author AffiliationIDS="Aff21"><AuthorName DisplayOrder="Western"><GivenName>Chunmei</GivenName><FamilyName>Liu</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff22"><AuthorName DisplayOrder="Western"><GivenName>Xiuzhen</GivenName><FamilyName>Huang</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff23"><AuthorName DisplayOrder="Western"><GivenName>Russell</GivenName><GivenName>L.</GivenName><FamilyName>Malmberg</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff24"><AuthorName DisplayOrder="Western"><GivenName>Ying</GivenName><FamilyName>Xu</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff21"><AuthorName DisplayOrder="Western"><GivenName>Liming</GivenName><FamilyName>Cai</FamilyName></AuthorName></Author><Affiliation ID="Aff21"><OrgDivision>Dept. of Computer Science</OrgDivision><OrgName>Univ. of Georgia</OrgName><OrgAddress><City>Athens</City><State>GA</State><Postcode>30602</Postcode><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff22"><OrgDivision>Dept. of Computer Science</OrgDivision><OrgName>Arkansas State Univ., State University</OrgName><OrgAddress><State>AR</State><Postcode>72467</Postcode><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff23"><OrgDivision>Dept. of Plant Biology</OrgDivision><OrgName>Univ. of Georgia</OrgName><OrgAddress><City>Athens</City><State>GA</State><Postcode>30602</Postcode><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff24"><OrgDivision>Dept. of Biochemistry and Molecular Biology</OrgDivision><OrgName>Univ. of Georgia</OrgName><OrgAddress><City>Athens</City><State>GA</State><Postcode>30602</Postcode><Country>USA</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases.</Para><Para>This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">k</Emphasis><Superscript><Emphasis Type="Italic">t</Emphasis></Superscript><Emphasis Type="Italic">N</Emphasis><Superscript>2</Superscript>) for the structure of <Emphasis Type="Italic">N</Emphasis> residues and its tree decomposition of width <Emphasis Type="Italic">t</Emphasis>. The parameter <Emphasis Type="Italic">k</Emphasis>, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></SubPart></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment</title></titleInfo><name type="personal"><namePart type="given">Yinglei</namePart><namePart type="family">Song</namePart><affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</affiliation><affiliation>E-mail: cai@cs.uga.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Chunmei</namePart><namePart type="family">Liu</namePart><affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Xiuzhen</namePart><namePart type="family">Huang</namePart><affiliation>Dept. of Computer Science, Arkansas State Univ., State University, 72467, AR, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Russell</namePart><namePart type="given">L.</namePart><namePart type="family">Malmberg</namePart><affiliation>Dept. of Plant Biology, Univ. of Georgia, 30602, Athens, GA, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Ying</namePart><namePart type="family">Xu</namePart><affiliation>Dept. of Biochemistry and Molecular Biology, Univ. of Georgia, 30602, Athens, GA, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Liming</namePart><namePart type="family">Cai</namePart><affiliation>Dept. of Computer Science, Univ. of Georgia, 30602, Athens, GA, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="proceedings" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005</dateIssued><copyrightDate encoding="w3cdtf">2005</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O(k t N 2) for the structure of N residues and its tree decomposition of width t. The parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.</abstract><relatedItem type="host"><titleInfo><title>Algorithms in Bioinformatics</title><subTitle>5th International Workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Rita</namePart><namePart type="family">Casadio</namePart><affiliation>Biocomputing Group, University of Bologna, Italy</affiliation><affiliation>E-mail: casadio@alma.unibo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gene</namePart><namePart type="family">Myers</namePart><affiliation>Janelia Farm Research Campus, Howard Hughes Medical Institute, Ashburn, Virginia, USA</affiliation><affiliation>E-mail: myersg@janelia.hhmi.org</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">2005</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I17036">Probability and Statistics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="L15001">Bioinformatics</topic></subject><identifier type="DOI">10.1007/11557067</identifier><identifier type="ISBN">978-3-540-29008-7</identifier><identifier type="eISBN">978-3-540-31812-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">126627</identifier><identifier type="BookID">978-3-540-31812-5</identifier><identifier type="BookChapterCount">35</identifier><identifier type="BookVolumeNumber">3692</identifier><identifier type="BookSequenceNumber">3692</identifier><identifier type="PartChapterCount">6</identifier><part><date>2005</date><detail type="part"><title>Structure</title></detail><detail type="volume"><number>3692</number><caption>vol.</caption></detail><extent unit="pages"><start>376</start><end>388</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2005</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>New York University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dough</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2005</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Bioinformatics</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>New York University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dough</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Sorin</namePart><namePart type="family">Istrail</namePart><affiliation>Celera Genomics, Applied Biosystems, Rockville, MD, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Pavel</namePart><namePart type="family">Pevzner</namePart><affiliation>University of California, San Diego, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Michael</namePart><namePart type="family">Waterman</namePart><affiliation>University of Southern California, Los Angeles, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Rita</namePart><namePart type="family">Casadio</namePart><affiliation>Biocomputing Group, University of Bologna, Italy</affiliation><affiliation>E-mail: casadio@alma.unibo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gene</namePart><namePart type="family">Myers</namePart><affiliation>Janelia Farm Research Campus, Howard Hughes Medical Institute, Ashburn, Virginia, USA</affiliation><affiliation>E-mail: myersg@janelia.hhmi.org</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SubSeriesID">5381</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2005</recordOrigin></recordInfo></relatedItem><identifier type="istex">F6316235B91C7ECC5DF547655E0F3533F36E03B0</identifier><identifier type="ark">ark:/67375/HCB-KDXGGF10-K</identifier><identifier type="DOI">10.1007/11557067_31</identifier><identifier type="ChapterID">31</identifier><identifier type="ChapterID">Chap31</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2005</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, 2005</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-KDXGGF10-K/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sante/explor/CovidV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000156 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000156 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sante
|area= CovidV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:F6316235B91C7ECC5DF547655E0F3533F36E03B0
|texte= Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment
}}
| This area was generated with Dilib version V0.6.33. |  |