Local multiple alignment via subgraph enumeration
Identifieur interne : 003371 ( Istex/Corpus ); précédent : 003370; suivant : 003372Local multiple alignment via subgraph enumeration
Auteurs : Z. Zhang ; B. He ; W. MillerSource :
- Discrete Applied Mathematics [ 0166-218X ] ; 1996.
Abstract
We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.
Url:
DOI: 10.1016/S0166-218X(96)00072-8
Links to Exploration step
ISTEX:F759384CE6EAAF135322A933E3A51E11EA7B623ALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Local multiple alignment via subgraph enumeration</title><author><name sortKey="Zhang, Z" sort="Zhang, Z" uniqKey="Zhang Z" first="Z." last="Zhang">Z. Zhang</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author><author><name sortKey="He, B" sort="He, B" uniqKey="He B" first="B." last="He">B. He</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author><author><name sortKey="Miller, W" sort="Miller, W" uniqKey="Miller W" first="W." last="Miller">W. Miller</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F759384CE6EAAF135322A933E3A51E11EA7B623A</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1016/S0166-218X(96)00072-8</idno><idno type="url">https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">003371</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Local multiple alignment via subgraph enumeration</title><author><name sortKey="Zhang, Z" sort="Zhang, Z" uniqKey="Zhang Z" first="Z." last="Zhang">Z. Zhang</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author><author><name sortKey="He, B" sort="He, B" uniqKey="He B" first="B." last="He">B. He</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author><author><name sortKey="Miller, W" sort="Miller, W" uniqKey="Miller W" first="W." last="Miller">W. Miller</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="ISSN">0166-218X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1996">1996</date><biblScope unit="volume">71</biblScope><biblScope unit="issue">1–3</biblScope><biblScope unit="page" from="337">337</biblScope><biblScope unit="page" to="365">365</biblScope></imprint><idno type="ISSN">0166-218X</idno></series><idno type="istex">F759384CE6EAAF135322A933E3A51E11EA7B623A</idno><idno type="DOI">10.1016/S0166-218X(96)00072-8</idno><idno type="PII">S0166-218X(96)00072-8</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0166-218X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>Z. Zhang</name><affiliations><json:string>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</json:string></affiliations></json:item><json:item><name>B. He</name><affiliations><json:string>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</json:string></affiliations></json:item><json:item><name>W. Miller</name><affiliations><json:string>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Sequence comparison</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Multiple alignment</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Subgraph enumeration</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Maximal clique</value></json:item></subject><language><json:string>eng</json:string></language><abstract>We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.</abstract><qualityIndicators><score>6.56</score><pdfVersion>1.2</pdfVersion><pdfPageSize>468 x 684 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>4</keywordCount><abstractCharCount>890</abstractCharCount><pdfWordCount>11143</pdfWordCount><pdfCharCount>59374</pdfCharCount><pdfPageCount>29</pdfPageCount><abstractWordCount>130</abstractWordCount></qualityIndicators><title>Local multiple alignment via subgraph enumeration</title><pii><json:string>S0166-218X(96)00072-8</json:string></pii><genre><json:string>research-article</json:string></genre><host><volume>71</volume><pii><json:string>S0166-218X(00)X0032-7</json:string></pii><pages><last>365</last><first>337</first></pages><issn><json:string>0166-218X</json:string></issn><issue>1–3</issue><genre><json:string>Journal</json:string></genre><language><json:string>unknown</json:string></language><title>Discrete Applied Mathematics</title><publicationDate>1996</publicationDate></host><categories><wos><json:string>MATHEMATICS, APPLIED</json:string></wos></categories><publicationDate>1996</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1016/S0166-218X(96)00072-8</json:string></doi><id>F759384CE6EAAF135322A933E3A51E11EA7B623A</id><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/fulltext/pdf</uri></json:item><json:item><original>true</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/fulltext/txt</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Local multiple alignment via subgraph enumeration</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Local multiple alignment via subgraph enumeration</title><author><persName><forename type="first">Z.</forename><surname>Zhang</surname></persName><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation></author><author><persName><forename type="first">B.</forename><surname>He</surname></persName><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation></author><author><persName><forename type="first">W.</forename><surname>Miller</surname></persName><note type="correspondence"><p>Corresponding author.</p></note><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation></author></analytic><monogr><title level="j">Discrete Applied Mathematics</title><title level="j" type="abbrev">DAM</title><idno type="pISSN">0166-218X</idno><idno type="PII">S0166-218X(00)X0032-7</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1996"></date><biblScope unit="volume">71</biblScope><biblScope unit="issue">1–3</biblScope><biblScope unit="page" from="337">337</biblScope><biblScope unit="page" to="365">365</biblScope></imprint></monogr><idno type="istex">F759384CE6EAAF135322A933E3A51E11EA7B623A</idno><idno type="DOI">10.1016/S0166-218X(96)00072-8</idno><idno type="PII">S0166-218X(96)00072-8</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Sequence comparison</term></item><item><term>Multiple alignment</term></item><item><term>Subgraph enumeration</term></item><item><term>Maximal clique</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1996-03-30">Registration</change><change when="1996-03-10">Modified</change><change when="1996">Published</change></revisionDesc></teiHeader></istex:fulltextTEI></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>DAM</jid><aid>96000728</aid><ce:pii>S0166-218X(96)00072-8</ce:pii><ce:doi>10.1016/S0166-218X(96)00072-8</ce:doi><ce:copyright type="unknown" year="1996"></ce:copyright></item-info><head><ce:title>Local multiple alignment via subgraph enumeration</ce:title><ce:author-group><ce:author><ce:given-name>Z.</ce:given-name><ce:surname>Zhang</ce:surname></ce:author><ce:author><ce:given-name>B.</ce:given-name><ce:surname>He</ce:surname></ce:author><ce:author><ce:given-name>W.</ce:given-name><ce:surname>Miller</ce:surname><ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup></ce:cross-ref></ce:author><ce:affiliation><ce:textfn>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>∗</ce:label><ce:text>Corresponding author.</ce:text></ce:correspondence></ce:author-group><ce:date-received day="24" month="5" year="1995"></ce:date-received><ce:date-revised day="10" month="3" year="1996"></ce:date-revised><ce:date-accepted day="30" month="3" year="1996"></ce:date-accepted><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>We discuss three problems, which we call <ce:italic>blocking, chaining</ce:italic> and <ce:italic>flattening</ce:italic>, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Sequence comparison</ce:text></ce:keyword><ce:keyword><ce:text>Multiple alignment</ce:text></ce:keyword><ce:keyword><ce:text>Subgraph enumeration</ce:text></ce:keyword><ce:keyword><ce:text>Maximal clique</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Local multiple alignment via subgraph enumeration</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Local multiple alignment via subgraph enumeration</title></titleInfo><name type="personal"><namePart type="given">Z.</namePart><namePart type="family">Zhang</namePart><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">B.</namePart><namePart type="family">He</namePart><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">W.</namePart><namePart type="family">Miller</namePart><affiliation>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802, USA</affiliation><description>Corresponding author.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1996</dateIssued><dateValid encoding="w3cdtf">1996-03-30</dateValid><dateModified encoding="w3cdtf">1996-03-10</dateModified><copyrightDate encoding="w3cdtf">1996</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">We discuss three problems, which we call blocking, chaining and flattening, that arise when computing a multiple-sequence alignment from given pairwise alignments. Blocking is the construction of gap-free multiple alignments, each called a “block”, from the pairwise alignments; it is formalized here as the enumeration of maximal cliques in a certain graph. Chaining is the identification of a collection of blocks that can appear together in a multiple alignment, which we formalize as determining a maximal connected subgraph (of a different graph) that satisfies certain consistency conditions. Flattening is the introduction of gaps within a chain of blocks to create a multiple alignment, which involves solving a problem of dynamic bipartite matching. For each problem, practical algorithms are presented and shown to be effective for analyzing sequences containing internal repeats.</abstract><subject><genre>Keywords</genre><topic>Sequence comparison</topic><topic>Multiple alignment</topic><topic>Subgraph enumeration</topic><topic>Maximal clique</topic></subject><relatedItem type="host"><titleInfo><title>Discrete Applied Mathematics</title></titleInfo><titleInfo type="abbreviated"><title>DAM</title></titleInfo><genre type="Journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19961205</dateIssued></originInfo><identifier type="ISSN">0166-218X</identifier><identifier type="PII">S0166-218X(00)X0032-7</identifier><part><date>19961205</date><detail type="volume"><number>71</number><caption>vol.</caption></detail><detail type="issue"><number>1–3</number><caption>no.</caption></detail><extent unit="issue pages"><start>1</start><end>368</end></extent><extent unit="pages"><start>337</start><end>365</end></extent></part></relatedItem><identifier type="istex">F759384CE6EAAF135322A933E3A51E11EA7B623A</identifier><identifier type="DOI">10.1016/S0166-218X(96)00072-8</identifier><identifier type="PII">S0166-218X(96)00072-8</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata><enrichments><istex:catWosTEI uri="https://api.istex.fr/document/F759384CE6EAAF135322A933E3A51E11EA7B623A/enrichments/catWos"><teiHeader><profileDesc><textClass><classCode scheme="WOS">MATHEMATICS, APPLIED</classCode></textClass></profileDesc></teiHeader></istex:catWosTEI></enrichments><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003371 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003371 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:F759384CE6EAAF135322A933E3A51E11EA7B623A
|texte= Local multiple alignment via subgraph enumeration
}}
| This area was generated with Dilib version V0.6.32. |  |