Models and algorithms for genome rearrangement with positional constraints

DOI10.1007/978-3-662-48221-6_18MaRDI QIDQ5283831zbMATH OpenOpenAlexFDO

Authors Krister M. Swenson, Mathieu Blanchette

Publication date 25 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348502/file/s13015-016-0065-9.pdf

zbMATH Keywords

rearrangementcircle graphscolored noncrossing partitions

Mathematics Subject Classification ID

Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Graph theory (including graph drawing) in computer science (68R10) Computational methods for problems pertaining to biology (92-08)

Recommendations

• Weighted Minimum-Length Rearrangement Scenarios.
• Finding Local Genome Rearrangements
• Sorting by Weighted Reversals, Transpositions, and Inverted Transpositions
• Genome rearrangements on both gene order and intergenic regions
• A linear time approximation algorithm for the DCJ distance for genomes with bounded number of duplicates

Cites work

• Algorithms and Computation
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An output sensitive algorithm for computing a maximum independent set of a circle graph
• Combinatorics of genome rearrangements.
• Improved bounds on sorting by length-weighted reversals
• The Exemplar Breakpoint Distance for Non-trivial Genomes Cannot Be Approximated

Cited in

(9)

• Optimizing Restriction Site Placement for Synthetic Genomes
• The complexity of genome rearrangement combinatorics under the infinite sites model
• A new algebraic approach to genome rearrangement models
• Finding Local Genome Rearrangements
• The Deletion-Insertion model applied to the genome rearrangement problem
• On weighting schemes for gene order analysis
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• scientific article; zbMATH DE number 1405677 (Why is no real title available?)
• Comparative Genomics

This page was built for publication: Models and algorithms for genome rearrangement with positional constraints

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