Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/104551
Title: Controlling size when aligning multiple genomic sequences with duplications
Authors: Hou, M.
Berman, P.
Zhang, L. 
Miller, W.
Issue Date: 2006
Citation: Hou, M.,Berman, P.,Zhang, L.,Miller, W. (2006). Controlling size when aligning multiple genomic sequences with duplications. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4175 LNBI : 138-149. ScholarBank@NUS Repository.
Abstract: For a genomic region containing a tandem gene cluster, a proper set of alignments needs to align only orthologous segments, i.e., those separated by a speciation event. Otherwise, methods for finding regions under evolutionary selection will not perform properly. Conversely, the alignments should indicate every orthologous pair of genes or genomic segments. Attaining this goal in practice requires a technique for avoiding a combinatorial explosion in the number of local alignments. To better understand this process, we model it as a graph problem of finding a minimum cardinality set of cliques that contain all edges. We provide an upper bound for an important class of graphs (the problem is 7 NP-hard and very difficult to approximate in the general case), and use the bound and computer simulations to evaluate two heuristic solutions. An implementation of one of them is evaluated on mammalian sequences from the α-globin gene cluster. © Springer-Verlag Berlin Heidelberg 2006.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/104551
ISBN: 3540395830
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

43
checked on Nov 9, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.