skip to main content
article

Removing Noise and Ambiguities from Comparative Maps in Rearrangement Analysis

Published: 01 October 2007 Publication History

Abstract

Comparison of genomic maps is hampered by errors and ambiguities introduced by mapping technology, incorrectly resolved paralogy, small samples of markers and extensive genome rearrangement. We design an analysis to remove or resolve most of these problems and to extract corrected data where markers occur in consecutive strips in both genomes. To do this we introduce the notion of pre-strip, an efficient way of generating these, and a compatibility analysis culminating in a Maximum Weighted Clique (MWC) search. The output can be directly analyzed with genome rearrangement algorithms, allowing the restoration of some of the data not incorporated into the clique solution. We investigate the trade-off between criteria for discarding excessive pre-strips to make MWC feasible, in terms of retaining as many markers as possible in the solution and producing an economical rearrangement analysis. We explore these questions through simulation and through comparison of the rice and sorghum genomes.

References

[1]
S. Arora, D. Karger, and M. Karpinski, “Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems,” J. Computer and System Sciences, vol. 58, pp. 193-210, 1999.
[2]
J.E. Bowers, C. Abbey, S. Anderson, C. Chang, X. Draye, A.H. Hoppe, R. Jessup, C. Lemke, J. Lennington, Z. Li, Y.R. Lin, S.C. Liu, L. Luo, B.S. Marler, R. Ming, S.E. Mitchell, D. Qiang, K. Reischmann, S.R. Schulze, D.N. Skinner, Y.W. Wang, S. Kresovich, K.F. Schertz, and A.H. Paterson, “A High-Density Genetic Recombination Map of Sequence-Tagged Sites for Sorghum, as a Framework for Comparative Structural and Evolutionary Genomics of Tropical Grains and Grasses,” Genetics, vol. 165, pp. 367-386, 2003.
[3]
Rice-Gramene Annotated Nipponbare Sequence, http://www.gramene.org/Oryza_sativa/, 2006.
[4]
S. Hannenhalli and P.A. Pevzner, “To Cut or Not to Cut (Applications of Comparative Physical Maps in Molecular Evolution),” Proc. Seventh Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 304-313, 1996.
[5]
J. Kececioglu and D. Sankoff, “Exact and Approximation Algorithms for the Inversion Distance between Two Permutations,” Proc. Fourth Combinatorial Pattern Matching Symp., A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, eds., pp. 87-105, 1993, full version in Algorithmica, vol. 13, pp. 180-210, 1995.
[6]
D. Kumlander, “A New Exact Algorithm for the Maximum-Weight Clique Problem Based on a Heuristic Vertex-Coloring and a Backtrack Search,” Proc. Fourth European Congress Math., 2005
[7]
G. Tesler, “Efficient Algorithms for Multichromosomal Genome Rearrangements,” J. Computer and System Sciences, vol. 65, pp. 587-609, 2002.
[8]
D. Ware, P. Jaiswal, J. Ni, X. Pan, K. Chang, K. Clark, L. Teytelman, S. Schmidt, W. Zhao, S. Cartinhour, S. McCouch, and L. Stein, “Gramene: A Resource for Comparative Grass Genomics,” Nucleic Acids Research, vol. 30, pp. 103-105, 2002.
[9]
S. Yancopoulos, O. Attie, and R. Friedberg, “Efficient Sorting of Genomic Permutations by Translocation, Inversion and Block Interchange,” Bioinformatics, vol. 21, pp. 3340-3346, 2005.
[10]
C. Zheng and D. Sankoff, “Rearrangement of Noisy Genomes,” Proc. 2006 Int'l Workshop Bioinformatics Research and Applications. Part II, V.N. Alexandrov et al., eds., pp. 791-798, 2006.

Cited By

View all
  • (2020)A novel parallel local search algorithm for the maximum vertex weight clique problem in large graphsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-04122-z24:5(3551-3567)Online publication date: 1-Mar-2020
  • (2018)A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphsComputers and Operations Research10.1016/j.cor.2017.09.02390:C(232-248)Online publication date: 1-Feb-2018
  • (2013)Maximal strip recovery problem with gapsJournal of Discrete Algorithms10.1016/j.jda.2012.12.00619(1-22)Online publication date: 1-Mar-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 4, Issue 4
October 2007
192 pages

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 2007
Published in TCBB Volume 4, Issue 4

Author Tags

  1. Maximum Weight Clique
  2. genome rearrangements
  3. rice
  4. sorghum
  5. synteny blocks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2020)A novel parallel local search algorithm for the maximum vertex weight clique problem in large graphsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-019-04122-z24:5(3551-3567)Online publication date: 1-Mar-2020
  • (2018)A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphsComputers and Operations Research10.1016/j.cor.2017.09.02390:C(232-248)Online publication date: 1-Feb-2018
  • (2013)Maximal strip recovery problem with gapsJournal of Discrete Algorithms10.1016/j.jda.2012.12.00619(1-22)Online publication date: 1-Mar-2013
  • (2012)An improved approximation algorithm for the complementary maximal strip recovery problemJournal of Computer and System Sciences10.1016/j.jcss.2011.10.01478:3(720-730)Online publication date: 1-May-2012
  • (2012)Exact and approximation algorithms for the complementary maximal strip recovery problemJournal of Combinatorial Optimization10.1007/s10878-010-9366-y23:4(493-506)Online publication date: 1-May-2012
  • (2011)An improved approximation algorithm for the complementary maximal strip recovery problemProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021922(46-57)Online publication date: 28-May-2011
  • (2011)Tractability and approximability of maximal strip recoveryProceedings of the 22nd annual conference on Combinatorial pattern matching10.5555/2018243.2018274(336-349)Online publication date: 27-Jun-2011
  • (2010)Inapproximability of maximal strip recovery: IIProceedings of the 4th international conference on Frontiers in algorithmics10.5555/1881195.1881203(53-64)Online publication date: 11-Aug-2010
  • (2010)Efficient exact and approximate algorithms for the complement of maximal strip recoveryProceedings of the 6th international conference on Algorithmic aspects in information and management10.5555/1880586.1880619(325-333)Online publication date: 19-Jul-2010
  • (2010)On the parameterized complexity of some optimization problems related to multiple-interval graphsProceedings of the 21st annual conference on Combinatorial pattern matching10.5555/1875737.1875749(125-137)Online publication date: 21-Jun-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media