Combinatorial Algorithms for Design of DNA Arrays

TitleCombinatorial Algorithms for Design of DNA Arrays
Publication TypeBook Chapters
Year of Publication2002
AuthorsHannenhalli S, Hubbell E, Lipshutz R, Pevzner P
EditorHoheisel J, Brazma A., Büssow K., Cantor C., Christians F., Chui G., Diaz R., Drmanac R., Drmanac S., Eickhoff H., Fellenberg K., Hannenhalli S, Hoheisel J., Hou A., Hubbell E., Jin H., Jin P., Jurinke C., Konthur Z., Köster H., Kwon S., Lacy S., Lehrach H., Lipshutz R., Little D., Lueking A., McGall G., Moeur B., Nordhoff E., Nyarsik L., Pevzner P., Robinson A., Sarkans U., Shafto J., Sohail M., Southern E., Swanson D., Ukrainczyk T., van den Boom D., Vilo J., Vingron M., Walter G., Xu C.
Book TitleChip TechnologyChip Technology
Series TitleAdvances in Biochemical Engineering/Biotechnology
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-43215-9

Optimal design of DNA arrays requires the development of algorithms with two-fold goals: reducing the effects caused by unintended illumination ( border length minimization problem ) and reducing the complexity of masks ( mask decomposition problem ). We describe algorithms that reduce the number of rectangles in mask decomposition by 20–30% as compared to a standard array design under the assumption that the arrangement of oligonucleotides on the array is fixed. This algorithm produces provably optimal solution for all studied real instances of array design. We also address the difficult problem of finding an arrangement which minimizes the border length and come up with a new idea of threading that significantly reduces the border length as compared to standard designs.