Linked Life Data

20431155

Source:http://linkedlifedata.com/resource/pubmed/id/20431155

Statements in which the resource exists as a subject.
PredicateObject
rdf:type
lifeskim:mentions
pubmed:issue
2
pubmed:dateCreated
2010-4-30
pubmed:abstractText
The problem of sorting by reciprocal translocations (abbreviated as SBT) arises from the field of comparative genomics, which is to find a shortest sequence of reciprocal translocations that transforms one genome Pi into another genome Gamma, with the restriction that Pi and Gamma contain the same genes. SBT has been proved to be polynomial-time solvable, and several polynomial algorithms have been developed. In this paper, we show how to extend Bergeron's SBT algorithm to include insertions and deletions, allowing to compare genomes containing different genes. In particular, if the gene set of Pi is a subset (or superset, respectively) of the gene set of Gamma, we present an approximation algorithm for transforming Pi into Gamma by reciprocal translocations and deletions (insertions, respectively), providing a sorting sequence with length at most OPT + 2, where OPT is the minimum number of translocations and deletions (insertions, respectively) needed to transform Pi into Gamma; if Pi and Gamma have different genes but not containing each other, we give a heuristic to transform Pi into Gamma by a shortest sequence of reciprocal translocations, insertions, and deletions, with bounds for the length of the sorting sequence it outputs. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by El Mabrouk which is used to sort two chromosomes with different gene contents by reversals, insertions, and deletions.
pubmed:grant
pubmed:language
eng
pubmed:journal
pubmed:citationSubset
IM
pubmed:status
MEDLINE
pubmed:issn
1557-9964
pubmed:author
pubmed:issnType
Electronic
pubmed:volume
7
pubmed:owner
NLM
pubmed:authorsComplete
Y
pubmed:pagination
365-74
pubmed:meshHeading
pubmed:articleTitle
Sorting genomes by reciprocal translocations, insertions, and deletions.
pubmed:affiliation
School of Applied Mathematics and Statistics, Shandong University at Weihai, Weihai 264209, PR China. qixingqin@163.com
pubmed:publicationType
Journal Article, Research Support, U.S. Gov't, Non-P.H.S., Research Support, N.I.H., Extramural