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. | ![]() |