Chaining algorithms for multiple genome comparison

DOI10.1016/J.JDA.2004.08.011MaRDI QIDQ2569405zbMATH OpenOpenAlexFDO

Authors Enno Ohlebusch, Mohamed Ibrahim Abouelhoda

Publication date 27 October 2005

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2004.08.011

zbMATH Keywords

multiple alignmentfragment-chaining algorithmsrange maximum query

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Nonnumerical algorithms (68W05) Cell biology (92C37)

Recommendations

• Multiple genome alignment: chaining algorithms revisited
• Publication:4886031
• Co-linear chaining with overlaps and gap costs
• Linear-space algorithms that build local alignments from fragments
• Local multiple alignment via subgraph enumeration

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1182924 (Why is no real title available?)
• scientific article; zbMATH DE number 910858 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• A priority queue in which initialization and queue operations takeO(loglogD) time
• An \(O(N^ 2 \log N)\) restriction map comparison and search algorithm
• Chaining algorithms for multiple genome comparison
• Multiple genome alignment: chaining algorithms revisited
• New Data Structures for Orthogonal Range Queries
• On computing all north-east nearest neighbors in the \(L_ 1\) metric
• Preserving order in a forest in less than logarithmic time and linear space
• Sparse dynamic programming II
• Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees

Cited in

(12)

• Efficient algorithm for the vertex connectivity of trapezoid graphs
• An efficient algorithm to solve the conditional covering problem on trapezoid graphs
• Counting the number of vertex covers in a trapezoid graph
• Multiple genome alignment: chaining algorithms revisited
• Sequence to graph alignment using gap-sensitive co-linear chaining
• Fast algorithms for computing tree LCS
• Fast Algorithms for Computing Tree LCS
• Aligning two fragmented sequences
• Chaining algorithms for multiple genome comparison
• Co-linear chaining with overlaps and gap costs
• Efficient Chaining of Seeds in Ordered Trees
• Distributed interactive proofs for the recognition of some geometric intersection graph classes

Describes a project that uses

Uses Software

• BLASTZ
• MUMMER
• LAGAN

This page was built for publication: Chaining algorithms for multiple genome comparison

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