Genomic distance under gene substitutions

Braga MDV, Machado R, Ribeiro LC, Stoye J (2011)
BMC Bioinformatics 12(Suppl 9: Proc. of RECOMB-CG 2011).

Download
OA
Journal Article | Published | English
Author
; ; ;
Abstract
Background: The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur at the same position of the genome count for two sorting steps. Results: Here we propose a new model that sorts non-common markers with substitutions, which are more powerful operations that comprehend insertions and deletions. A deletion and an insertion that occur at the same position of the genome can be modeled as a substitution, counting for a single sorting step. Conclusions: Comparing genomes with unequal content, but without duplicated markers, we give a linear time algorithm to compute the genomic distance considering substitutions and double-cut-and-join (DCJ) operations. This model provides a parsimonious genomic distance to handle genomes free of duplicated markers, that is in practice a lower bound to the real genomic distances. The method could also be used to refine orthology assignments, since in some cases a substitution could actually correspond to an unannotated orthology.
Publishing Year
ISSN
PUB-ID

Cite this

Braga MDV, Machado R, Ribeiro LC, Stoye J. Genomic distance under gene substitutions. BMC Bioinformatics. 2011;12(Suppl 9: Proc. of RECOMB-CG 2011).
Braga, M. D. V., Machado, R., Ribeiro, L. C., & Stoye, J. (2011). Genomic distance under gene substitutions. BMC Bioinformatics, 12(Suppl 9: Proc. of RECOMB-CG 2011).
Braga, M. D. V., Machado, R., Ribeiro, L. C., and Stoye, J. (2011). Genomic distance under gene substitutions. BMC Bioinformatics 12.
Braga, M.D.V., et al., 2011. Genomic distance under gene substitutions. BMC Bioinformatics, 12(Suppl 9: Proc. of RECOMB-CG 2011).
M.D.V. Braga, et al., “Genomic distance under gene substitutions”, BMC Bioinformatics, vol. 12, 2011.
Braga, M.D.V., Machado, R., Ribeiro, L.C., Stoye, J.: Genomic distance under gene substitutions. BMC Bioinformatics. 12, (2011).
Braga, Marília D. V., Machado, Raphael, Ribeiro, Leonardo C., and Stoye, Jens. “Genomic distance under gene substitutions”. BMC Bioinformatics 12.Suppl 9: Proc. of RECOMB-CG 2011 (2011).
Main File(s)
Access Level
OA Open Access
Last Uploaded
2012-02-07 15:29:45

This data publication is cited in the following publications:
This publication cites the following data publications:

3 Citations in Europe PMC

Data provided by Europe PubMed Central.

Orthology detection combining clustering and synteny for very large datasets.
Lechner M, Hernandez-Rosales M, Doerr D, Wieseke N, Thevenin A, Stoye J, Hartmann RK, Prohaska SJ, Stadler PF., PLoS ONE 9(8), 2014
PMID: 25137074
DCJ-indel and DCJ-substitution distances with distinct operation costs.
da Silva PH, Machado R, Dantas S, Braga MD., Algorithms Mol Biol 8(1), 2013
PMID: 23879938
On the weight of indels in genomic distances.
Braga MD, Machado R, Ribeiro LC, Stoye J., BMC Bioinformatics 12 Suppl 9(), 2011
PMID: 22151784

13 References

Data provided by Europe PubMed Central.

A unifying view of genome rearrangements
AUTHOR UNKNOWN, 2006
The solution space of sorting by DCJ.
Braga MD, Stoye J., J. Comput. Biol. 17(9), 2010
PMID: 20874401
Transforming men into mice (polynomial algorithm for genomic distance problem)
AUTHOR UNKNOWN, 1995
Sorting Signed Permutations by Reversals and Insertions/Deletions of Contiguous Segments
AUTHOR UNKNOWN, 2001
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
The duplication/random loss model for gene rearrangement exemplified by mitochondrial genomes of deuterostome animals
AUTHOR UNKNOWN, 2000
Evolution of animal mitochondrial DNA: relevance for population biology and systematics
AUTHOR UNKNOWN, 1987
The DNA sequence of the human X chromosome.
Ross MT, Grafham DV, Coffey AJ, Scherer S, McLay K, Muzny D, Platzer M, Howell GR, Burrows C, Bird CP, Frankish A, Lovell FL, Howe KL, Ashurst JL, Fulton RS, Sudbrak R, Wen G, Jones MC, Hurles ME, Andrews TD, Scott CE, Searle S, Ramser J, Whittaker A, Deadman R, Carter NP, Hunt SE, Chen R, Cree A, Gunaratne P, Havlak P, Hodgson A, Metzker ML, Richards S, Scott G, Steffen D, Sodergren E, Wheeler DA, Worley KC, Ainscough R, Ambrose KD, Ansari-Lari MA, Aradhya S, Ashwell RI, Babbage AK, Bagguley CL, Ballabio A, Banerjee R, Barker GE, Barlow KF, Barrett IP, Bates KN, Beare DM, Beasley H, Beasley O, Beck A, Bethel G, Blechschmidt K, Brady N, Bray-Allen S, Bridgeman AM, Brown AJ, Brown MJ, Bonnin D, Bruford EA, Buhay C, Burch P, Burford D, Burgess J, Burrill W, Burton J, Bye JM, Carder C, Carrel L, Chako J, Chapman JC, Chavez D, Chen E, Chen G, Chen Y, Chen Z, Chinault C, Ciccodicola A, Clark SY, Clarke G, Clee CM, Clegg S, Clerc-Blankenburg K, Clifford K, Cobley V, Cole CG, Conquer JS, Corby N, Connor RE, David R, Davies J, Davis C, Davis J, Delgado O, Deshazo D, Dhami P, Ding Y, Dinh H, Dodsworth S, Draper H, Dugan-Rocha S, Dunham A, Dunn M, Durbin KJ, Dutta I, Eades T, Ellwood M, Emery-Cohen A, Errington H, Evans KL, Faulkner L, Francis F, Frankland J, Fraser AE, Galgoczy P, Gilbert J, Gill R, Glockner G, Gregory SG, Gribble S, Griffiths C, Grocock R, Gu Y, Gwilliam R, Hamilton C, Hart EA, Hawes A, Heath PD, Heitmann K, Hennig S, Hernandez J, Hinzmann B, Ho S, Hoffs M, Howden PJ, Huckle EJ, Hume J, Hunt PJ, Hunt AR, Isherwood J, Jacob L, Johnson D, Jones S, de Jong PJ, Joseph SS, Keenan S, Kelly S, Kershaw JK, Khan Z, Kioschis P, Klages S, Knights AJ, Kosiura A, Kovar-Smith C, Laird GK, Langford C, Lawlor S, Leversha M, Lewis L, Liu W, Lloyd C, Lloyd DM, Loulseged H, Loveland JE, Lovell JD, Lozado R, Lu J, Lyne R, Ma J, Maheshwari M, Matthews LH, McDowall J, McLaren S, McMurray A, Meidl P, Meitinger T, Milne S, Miner G, Mistry SL, Morgan M, Morris S, Muller I, Mullikin JC, Nguyen N, Nordsiek G, Nyakatura G, O'Dell CN, Okwuonu G, Palmer S, Pandian R, Parker D, Parrish J, Pasternak S, Patel D, Pearce AV, Pearson DM, Pelan SE, Perez L, Porter KM, Ramsey Y, Reichwald K, Rhodes S, Ridler KA, Schlessinger D, Schueler MG, Sehra HK, Shaw-Smith C, Shen H, Sheridan EM, Shownkeen R, Skuce CD, Smith ML, Sotheran EC, Steingruber HE, Steward CA, Storey R, Swann RM, Swarbreck D, Tabor PE, Taudien S, Taylor T, Teague B, Thomas K, Thorpe A, Timms K, Tracey A, Trevanion S, Tromans AC, d'Urso M, Verduzco D, Villasana D, Waldron L, Wall M, Wang Q, Warren J, Warry GL, Wei X, West A, Whitehead SL, Whiteley MN, Wilkinson JE, Willey DL, Williams G, Williams L, Williamson A, Williamson H, Wilming L, Woodmansey RL, Wray PW, Yen J, Zhang J, Zhou J, Zoghbi H, Zorilla S, Buck D, Reinhardt R, Poustka A, Rosenthal A, Lehrach H, Meindl A, Minx PJ, Hillier LW, Willard HF, Wilson RK, Waterston RH, Rice CM, Vaudin M, Coulson A, Nelson DL, Weinstock G, Sulston JE, Durbin R, Hubbard T, Gibbs RA, Beck S, Rogers J, Bentley DR., Nature 434(7031), 2005
PMID: 15772651
On the weight of indels in genomic distances.
Braga MD, Machado R, Ribeiro LC, Stoye J., BMC Bioinformatics 12 Suppl 9(), 2011
PMID: 22151784

AUTHOR UNKNOWN, 1967
Four evolutionary strata on the human X chromosome.
Lahn BT, Page DC., Science 286(5441), 1999
PMID: 10542153

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 22151231
PubMed | Europe PMC

Search this title in

Google Scholar