TY - GEN
T1 - Of mice and men
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
AU - Kececioglu, John D.
AU - Ravi, R.
N1 - Funding Information:
‘work carried out while the authors were at the Department of Computer Science of the University of California, Davis. iDepartment of Computer Science, The University of Georgia, Athens, GA 30602. Electronic mail: kecoQcs.uga.sdu. This research was supported by a DOE Human Genome Distinguished Postdoctoral Fellowship. tDepartment of Computer Science, Princeton University, Princeton, NJ 08544. Electronic mail: ravi@cs .prinoeton. l du. Research supported by DOE Grant DEFG03-90ER60999 and a DIMACS Postdoctoral Fellowship.
PY - 1995/1/22
Y1 - 1995/1/22
N2 - A new and largely unexplored area of computational biology is combinatorial algorithms for genome rearrangement. In the course of its evolution, the genome of an organism mutates by processes that can rearrange whole segments of a chromosome in a single event. These rearrangement mechanisms include inversion, transposition, duplication, and translocation, and a basic problem is to determine the minimum number of such events that transform one genome to another. This number is called the rearrangement distance between the two genomes, and gives a lower bound on the number of events that must have occurred since their divergence, assuming evolution proceeds according to the processes of the study.In this paper, we begin the algorithmic study of genome rearrangement by translocation. A transloca^ tion exchanges material at the end of two chromosomes within a genome. We model this as a process that exchanges prefixes and suffixes of strings, where each string represents a sequence of distinct markers along a chromosome in the genome. For the general problem of determining the translocation distance between two such sets of strings, we present a 2-approximation algorithm. For a theoretical model in which the exchanged substrings are of equal length, we derive an optimal algorithm for translocation distance. We also examine for the first time two types of rearrangements in concert. An inversion reverses the order of markers within a substring, and flips the orientation of the markers. For genomes that have evolved by translocation and inversion, we show there is a simple 2-approximation algorithm for data in which the orientation of markers is unknown, and a |-approximation algorithm when orientation is known. These results take a step towards extending the area from the analysis of simple organisms, whose genomes consist of a single chromosome, and whose evolution has largely involved a single type of rearrangement event, to the analysis of organisms such as man and mouse, whose genomes contain many chromosomes, and whose history since divergence has largely consisted of inversion and translocation events.
AB - A new and largely unexplored area of computational biology is combinatorial algorithms for genome rearrangement. In the course of its evolution, the genome of an organism mutates by processes that can rearrange whole segments of a chromosome in a single event. These rearrangement mechanisms include inversion, transposition, duplication, and translocation, and a basic problem is to determine the minimum number of such events that transform one genome to another. This number is called the rearrangement distance between the two genomes, and gives a lower bound on the number of events that must have occurred since their divergence, assuming evolution proceeds according to the processes of the study.In this paper, we begin the algorithmic study of genome rearrangement by translocation. A transloca^ tion exchanges material at the end of two chromosomes within a genome. We model this as a process that exchanges prefixes and suffixes of strings, where each string represents a sequence of distinct markers along a chromosome in the genome. For the general problem of determining the translocation distance between two such sets of strings, we present a 2-approximation algorithm. For a theoretical model in which the exchanged substrings are of equal length, we derive an optimal algorithm for translocation distance. We also examine for the first time two types of rearrangements in concert. An inversion reverses the order of markers within a substring, and flips the orientation of the markers. For genomes that have evolved by translocation and inversion, we show there is a simple 2-approximation algorithm for data in which the orientation of markers is unknown, and a |-approximation algorithm when orientation is known. These results take a step towards extending the area from the analysis of simple organisms, whose genomes consist of a single chromosome, and whose evolution has largely involved a single type of rearrangement event, to the analysis of organisms such as man and mouse, whose genomes contain many chromosomes, and whose history since divergence has largely consisted of inversion and translocation events.
UR - http://www.scopus.com/inward/record.url?scp=84878713670&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84878713670&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84878713670
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 604
EP - 613
BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PB - Association for Computing Machinery
Y2 - 22 January 1995 through 24 January 1995
ER -