Local multiple alignment via subgraph enumeration
Identifieur interne : 001A66 ( Istex/Checkpoint ); précédent : 001A65; suivant : 001A67Local multiple alignment via subgraph enumeration
Auteurs : Z. Zhang [États-Unis] ; B. He [États-Unis] ; W. Miller [États-Unis]Source :
- 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
Affiliations:
Links toward previous steps (curation, corpus...)
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></author><author><name sortKey="He, B" sort="He, B" uniqKey="He B" first="B." last="He">B. He</name></author><author><name sortKey="Miller, W" sort="Miller, W" uniqKey="Miller W" first="W." last="Miller">W. Miller</name></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><idno type="wicri:Area/Istex/Curation">003117</idno><idno type="wicri:Area/Istex/Checkpoint">001A66</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 wicri:level="4"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">University Park (Pennsylvanie)</settlement></placeName><orgName type="university">Université d'État de Pennsylvanie</orgName></affiliation></author><author><name sortKey="He, B" sort="He, B" uniqKey="He B" first="B." last="He">B. He</name><affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">University Park (Pennsylvanie)</settlement></placeName><orgName type="university">Université d'État de Pennsylvanie</orgName></affiliation></author><author><name sortKey="Miller, W" sort="Miller, W" uniqKey="Miller W" first="W." last="Miller">W. Miller</name><affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802</wicri:regionArea><placeName><region type="state">Pennsylvanie</region><settlement type="city">University Park (Pennsylvanie)</settlement></placeName><orgName type="university">Université d'État de Pennsylvanie</orgName></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><affiliations><list><country><li>États-Unis</li></country><region><li>Pennsylvanie</li></region><settlement><li>University Park (Pennsylvanie)</li></settlement><orgName><li>Université d'État de Pennsylvanie</li></orgName></list><tree><country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Zhang, Z" sort="Zhang, Z" uniqKey="Zhang Z" first="Z." last="Zhang">Z. Zhang</name></region><name sortKey="He, B" sort="He, B" uniqKey="He B" first="B." last="He">B. He</name><name sortKey="Miller, W" sort="Miller, W" uniqKey="Miller W" first="W." last="Miller">W. Miller</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A66 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 001A66 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Istex
|étape= Checkpoint
|type= RBID
|clé= ISTEX:F759384CE6EAAF135322A933E3A51E11EA7B623A
|texte= Local multiple alignment via subgraph enumeration
}}
| This area was generated with Dilib version V0.6.32. |  |