Local multiple alignment via subgraph enumeration

DOI10.1016/S0166-218X(96)00072-8MaRDI QIDQ5961633zbMATH OpenFDO

Authors Z. Zhang, B. He, W. Miller

Publication date 11 November 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

blockingchainingflatteningmaximal cliquemolecular biologymultiple alignmentssequence comparisonsubgraph enumeration

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to biology (92-04) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40)

Recommendations

• Multiple Alignment, Communication Cost, and Graph Matching
• Partially local multi-way alignments
• On graph-based data structures to multiple genome alignment
• On the complexity of sequence to graph alignment
• An Eulerian path approach to local multiple alignment for DNA sequences
• Computational and Information Science
• On the number of many-to-many alignments of multiple sequences
• scientific article; zbMATH DE number 2086217

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A time-efficient, linar-space local similarity algorithm
• Algorithm 457: finding all cliques of an undirected graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Efficient Algorithms for Listing Combinatorial Structures
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 910858 (Why is no real title available?)
• Linear-space algorithms that build local alignments from fragments
• Multiple sequence comparison and consistency on multipartite graphs
• On generating all maximal independent sets
• Sparse dynamic programming II

Cited in

(13)

• Multiple sequence comparison and consistency on multipartite graphs
• Partially local multi-way alignments
• Neighborhood functions and hill-climbing strategies dedicated to the generalized ungapped local multiple alignment
• Chaining algorithms for multiple genome comparison
• scientific article; zbMATH DE number 1615272 (Why is no real title available?)
• Multiple Alignment, Communication Cost, and Graph Matching
• scientific article; zbMATH DE number 1746434 (Why is no real title available?)
• scientific article; zbMATH DE number 2087049 (Why is no real title available?)
• Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)
• Multiple alignment of biological sequences with gap flexibility
• CompBioNet 2004: algorithms \& computational methods for biochemical and evolutionary networks. Proceedings of the conference, Recife, Brazil, December 15--18, 2004.
• Comparative Genomics
• A heuristic algorithm for multiple sequence alignment based on blocks

Describes a project that uses

Uses Software

• ClustalW
• Algorithm 457

This page was built for publication: Local multiple alignment via subgraph enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961633)