■
a
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CỘNG NGHỆ
—£□—
Tên đề tài
PHƯƠNG PHÁP MỚI SẲP XỂP CẶP ĐÔI VỚI GHÉP ĐẢO CHỎ
Mã số: QC.09.03
Chủ nhiệm đề tài: 16. Lê Sỹ Vinh
ĐẠ! HỌC QUỐC GIA HÀ NỘI
TRUNS TẨM THÔNG TIN THƯ VIÊN
Hà Nội, 2010
Mục lục
1. Danh sách những người tham gia thực hiện đề tài 2
2. Tóm tắt các kết quả nghiên cứu chính của đề tài
3
3. Báo cáo’tổng kết 4
3.1. Đặt vấn đề 4
3.2. Tổng quan vấn đề nghiên cứu 4
3.3. Mục tiêu 6
3.4. Phương pháp đề xuất

7
3.4.1 Cơ sở lý thuyết 7
3.4.2 Các phương pháp hiện tại 8
3.4.3 Phương pháp đề xuất 11
3.4.4 Kết quả 13
3.5. Địa điểm, thời gian 13
ị. Tài liệu tham khảo 14
I -V HOC QUÕC GIA HA NỘI
TPƯNG TÂM THÒNG TIN THU VIỆN

1 OOOẼ 0 0 0 0 0 o i l
I
l.Danh sách những người tham gia thực hiện đề tài
TT
Tên
Học vị
Vai trò
Cơ quan
1
Lê Sỹ Vinh
TS Chủ nhiệm ĐHCN
2
Đặng Cao Cường
NCS Thành viên
ĐHCN
3
Đinh Ngọc Thắng
NCS Thành viên
University of Florida
4
Hà Tuấn Cường
sv
Thành viên
ĐHCN
5
Phạm Thị Mai Bảo
Chuyến viên Thư kí ĐHCN
2
2 Tóm tắt các kết quả nghiên cứu chính của đề tài
Kết quả khoa học: Đề tài đã tìm hiểu và nghiên cứu bài toán sắp xếp cặp đôi với phép đảo

chỗ (hay còn gọi là bắt cặp trình tự hệ gen với phép đổi chỗ). Chúng tôi đê xuât một phương
pháp mới giải quyết bài toán ừên với độ phức tạp là o (n2) so với độ phức tạp của các thuật
toán hiện tại là o (n 4). Kết quả thực nghiệm với dữ liệu thật và dừ liệu mô phỏng cho thấy
phương pháp mói cho kết quả tốt nhất cả về độ chính xác và thời gian chạy so với các
phương pháp hiện tại. Kết quà nghiên cứu được trình bày trong báo cáo khoa học với tiêu đê
“FS: A Fast Algorithm for Genome Rearrangements”, đã được chấp nhận đàng tại hội nghị
quốc tế “International conference on Bioinformatics, Computational biology- Genomics, and
Chemoinformatics” vào 12-14/7/2010 tại thành phố Florida, Hoa Kỳ
' o/bcbgc/index.html).
'íết quả phục vụ thực tế: Đề tài đã xây dựng phần mềm cho phép các nhà khoa học (đặc biệt
ác nhà sinh học) phân tích toàn bộ hai hệ gen có kích thước vừa và nhỏ. Đây là sàn phâm đáu
ên có chức năng như vậy ừên thế giới.
et quả đào tạo: Một khóa ỉuận tốt nghiệp với kết quả xuất sắc.
3
3. Báo cáo tổng kết
Đặt vấn đề
Với sự phát triển nhanh chóng của công nghệ sinh học, đặc biệt là công nghệ giải mã gen
cũng như toàn bộ hệ gen, một lượng lớn hệ gen đã được giải mã và lun giữ tại cơ sờ dữ
liệu gen quốc tế ( Sự phát triển b ù n g nổ cùa số
lượng hệ gen được giải mã đã đặt. ra nhiều bài toán mới và quan trọng trong tin sinh học
nhằm phân tích và so sánh các hệ gene.
Sắp xếp cặp đôi với phép đổi chồ là một bài toán mới và quan trọng trong tin sinh học.
Giải quyết bài toán ửên là nền tảng để giải quyết một loạt các bài toán quan trọng khác
như sắp xếp các bộ gene, phân tích mối quan hệ giữa các bộ gene, xây dựng cây tiến hóa
dựa vào các gene. Hiện nay, bài toán đã được mô hình hóa toán học bởi Vinh và đồng
nghiệp [1,2, 3]. Nhóm tác giả đã đề xuất một số phương pháp gần đúng để giải bài toán
trên. Độ phức tạp của các thuật thuật đề xuất là 0(n4) với n là số lượng gen trong một hệ
gene. Độ phức tạp này là lớn dẫn đến thuật toán không làm việc được với những hệ gen
có kích thước vừa và lớn.
Đề tài tập trung vào nghiên cứu một phương pháp mới có độ phức tạp thấp nhưng vẫn

cho kết quà với độ chính xác cao. Phương pháp này sẽ cho phép chúng ta tiến hành sẳp
xếp hai hệ gen một cách nhanh và hiệu quả.
Tong quan vấn đề nghiên cứu
Tat cả các sinh vật đều tiến hóa từ một tổ tiên chung, Trong quá trình tiến hóa, các biến
đoi trong hệ gen đã dẫn đến sự khác biệt giữa các hệ gene. Sự khác biệt giữa các hệ gen
đã tạo ra các loài sinh vật khác nhau cũng như sự khác nhau giữa các sinh vật trong cùng
một loài.
Các bien đoi trong hệ gen diễn ra ở hai mức độ khác nhau: mức độ điểm và mức độ gene.
Tai mức độ điểm, các biến đổi được gọi là biến đổi điểm (point mutation) bao gồm ba
loại chính là: thay thế dna, chèn dna, hay xóa dna.
Bên cạnh quá trình biến đổi ở mức độ điểm, sự khác biệt giữa các hệ gen còn do sự biến
đổi ở mức độ gen. Có ba phép biến đổi phổ biến là: chèn gen, xóa gen, và dịch chuyên
gen. Hmh 1 mô tả một ví dụ về sự biến đổi ở mức độ gen giữa Người và Khi.
Hai quá trình biến đổi trên dẫn đến hệ gen của các sinh vật ngày nay khác nhau về kích
thước, số lượng gene, thứ tự các gene, và nội dung của các gene.
12 3 4
Người
Khỉ
2 3 4 1
Hĩnh ỉ: Các biến đổi ở mức độ gen giữa Người và Khi
Khi so sánh và bắt cặp cho hai hệ gen, chúng ta cần tính đến các biến đổi ờ cả mức độ
điểm và mức độ gen. Việc bắt cặp hai hệ gen như vậy cho phép xây dựng bức tranh toàn
cảnh về sự tương tự và tiến hóa giữa các sinh vật, qua đó cho phép nâng cao dộ chính xác
dự đoán gene. Thời gian thực hiện là một vấn đề hết sức quan trọng do kích thước rất lớn
của các hệ gen.
Một trong những hệ thống bắp cặp hệ gen đầu tiên ỉà BLASTZ [4], dùng để bẳt cặp hệ
gen của người và chuột. BLASTZ có khả năng xác định và bắt cặp nhừng vùng ADN
tương đồng giữa người và chuột đồng thời cho phép các đoạn dna dịch chuyển vị trí trên
hệ gen (reaưangement). Tiếp theo BLASTZ, nhóm tác giả Darling tại đại học
Wisconsin-Madison nghiên cứu xây dựng hệ thống MAUVE để sấp hàng đa hệ gen và

thu được những kết quả có độ chính xác cao trên những hệ gen có độ tương đồng cao [5],
Bên cạnh đó, nhóm tác giả Brudno tại đại học Standford phát triển hệ thống SLAGAN
[6], Kết quả so sánh hai hệ thống MAUVE và SLAGAN cho thấy MAƯVE tốt hơn
SLAGAN trên những tập dữ liệu cỏ độ tương đồng cao, còn SLAGAN cho kết quà tốt
5
hơn MAƯVE ứên những tập dữ liệu tồn tại nhiều phép thay thế dna ỡ mức độ điểm và ít
phép đảo chiều đoạn dna ở mức độ gene.
Mặc dù nhiều phương pháp đã được đề xuất, chúng chủ yếu tập trung vào xác định và
bắt cặp cho những vùng dna có độ tương đồng cao giữa hai hệ gene. Tức là, một phần
lớn trorig hệ gen có thể không được bắt cặp và so sánh khi ta tiến hành với các loài sinh
vật có hệ gen khác nhau nhiều.
Với mục tiêu bắt cặp toàn bộ hệ gene, Vinh và đồng nghiệp đã mô hình toán học bài toán
trên với tên gọi “sắp xếp cặp đôi với phép đảo chỗ” [1]. Vinh và đồng nghiệp [1] đã đề
xuất ba phương pháp để giải quyết bài toán trên: (1) “stepwise addition”, (2) “character
moving” và (3) “simultaneous character swapping”. Trong ba phương pháp trên,
phương pháp “simultaneous character swapping” cho kết quả tốt nhất. Độ phức tạp của
các thuật toán đề xuất là 0(n 4) với n là số gen trong một hệ gene.
Muc tiêu
Độ phức tạp của các thuật toán đã được đề xuất, 0(n4), là rất lớn và chi có thể áp dụng
cho các hệ gen có kích thước nhỏ. Đề tài này tập trung vào phát triển một phương pháp
mới để giải quyết bài toán trên với độ phức tạp 0 (n ). Kết quả này sẽ giúp chúng ta phân
tích một lượng lớn dữ liệu trong thời gian cho phép.
Đề tài tập trung nghiên cứu những nội dung chính sau:
- Sự tiến hóa và các phép biến đổi trên hệ gene
- Bài toán sắp xếp hai hệ gen với phép đảo chỗ
- Các phương pháp hiện tại để giải quyết bài toán trên
- Phát triển phương pháp giải quyết bài toán ưên với độ phức tạp o (n2)
- Cài đặt và thử nghiệm thuật toán
- Viết báo cáo kết quả tại hội nghị quốc tế
6

Phương pháp đề xuất
3.4.1 Cơ sở lý thuyết
Trong bài toán sắp xếp cặp đôi với phép đảo chỗ, ta xem hai hệ gen như hai chuỗi ký tụ,
tức la mỗi đoạn gen sẽ được xem như là một ký tự trong chuỗi đầu vào. Ta gọi hai chuỗi
đầu vào là.JC= (xị X2' Xp) gồm/? ký tự, và Y = iy, y2, ■ ", yq) gồm q ký tự.
Ta gọi C{x„ yj) là chi phí để thay thể ký tự X, thành ký tự ỳ'j với 2=1 .p, j= 1 q. Khi
thực hiện với hai hệ gen, ta có X, và y} là hai chuỗi dna, khi đó chi phí C(x, yj) là chi phí
n h ỏ nhất đ ể b iế n đ ổ i X, thà n h y>j v à có th ể th ự c hiệ n b ằn g thuật toá n quy h oạ ch đ ộn g v ớ i
độ phức tạp là o ipq). Ta gọi C(x, y0) và C(x0 yị) là chi phí chèn/xóa kí tự X, và V) tương
ứng.
Gọi RỢ , Yr) là hàm chi phí đảo chỗ giữa các kí tự thuộc Y và một hoán vị YR cùa Y. R{Y,
Yr) có thể được tính theo khoảng cách “breakpoint” [9] hoặc tính theo khoảng cách
“inversion” [8].
Một chuỗiX 1 — ÌXị’, X2 , được gọi là một chuỗi phát triển (edited sequence) từ X
khi và chỉ khiX thu được từ X ’ sau khi xóa hết các ký tự Ví d ụX ' = 1, 2, 3, 4)
ỉà một chuỗi phát triển từ X - (1,2,3,4). Một cặp A = (X ’, Y ’) của hai chuồi X ’ = ( X ; x2
Xk’) phát ưiển và Y ’ = (yỊ y 2’, yic’) phát triển từ Y được gọi là một bắt cặp
hoàn chỉnh của X và Y. Một cách bắt cặp được xây dựng bàng cách chèn thêm ký tự ở
cả hai chuỗi (thứ tự các ký tự ừong chuồi không thay đổi).
Chi phí C(A) của một bắt cặp A là tổng chi phí thay thế và chèn/xóa của các ký tự trong
X \k Y,
Chi phí tối ưu để bắt cặp A (x \ Y ’) = argminA(^ Y'){C(A)} có thể được tính với độ phức
tạp thời gian là 0{pq) sử dụng kỹ thuật quy hoạch động.
k
(1)
7
Một chuỗi Xr = (xị x2\ xk’) được gọi là một chuỗi phát triển có sắp xếp lại (edited
rearrangement sequence) tù X nếu sau khi loại bỏ dấu ở XR’ ta thu được XR là một
hoán vị củaX. Ví dụ X R’ = 1, 4, 2, 3) là một chuỗi phát triển có sắp xếp lại từ
x= (1,2,3,4).

Một cặp A r = (XR Yr') của hai chuỗi phát triển có sắp xếp lạiX R' = (xì \ x2 \ ■ ■ ■, xk ’) và
Yr ’ = (y ị ’ y 2\ yk’) được gọi là một bắt cặp trình tự có sắp xếp lại (PAR) cùa hai
chuỗi X và Y. Chi phí CrCAr) của A r là tổng các chi phí thay thế giữa các ký tự, chi phí
chèn/xóa các kí tự và chi phí sắp' xếp lại giữa các ký tự. Ta có công thức:
Mục đích củ a b à i toàn sắ p x ế p cặp đô i v ớ i p h ép đ ổi ch ỗ là tìm A r có chi p h í n h ỏ nhất.
3.4.2 Các phương pháp hiện tại
Sắp xếp cặp đôi với phép đảo chỗ được cho là bài toán NP-Hard [1]. Vinh và đồng
nghiệp đã đề xuất các thuật toán tối ưu gần đúng theo chiến lược leo đồi để tìm ra cặp
PARAr*.
Thuật toán “stepwise addition”
Tư tưởng của thuật toán “stepwise addition” là từng bước xây dựng nghiệm đầy đủ từ
nghiệm chưa đầy đủ. Cụ thể là, chúng ta khởi đầu với một PAR chưa đầy đủ là
Aft=(XR’=X, Yr ’ = 0). Sau đó ta lần lượt chèn các ký tự y} E Y ,j - 1 |K| vào Yp' để tạo
thành một PAR đầy đủ. Ký tự yj được thêm vào vị trí sao cho chi phí cùa Afí mới là nhỏ
nhất. Thuật toán được mô tả như sau:
Stepwise addition method
k
(2)
A*r = a r g m in AE {C,ÍAR)3
I Yr <-
0
8
2 fo r j = 1 to \Y\
3 BestCost <— +00, BestPosition <— nil
4 fo r each position p in YR do
5 Insert yj into Yr at position p
6 Ar ^ A * (X ,Y r)
7 if Cr(Ar) < BestCost then
8 - ' BestPosition <—p, BestCost <— Cr(Ar)
9 Remove yj from Yr

10 endfor
11 Insert }>j into Yr at BestPosition
12 endfor
13 Return Ar = a (X, Yr)
Thuật toán “character moving”
Thuật toán “character moving” sử dụng tư tường của thuật toán leo đồi để giảm chi phí
Cr(A r ) c ủ a nghiệm tìm được từ thuật toán “Stepwise a d d itio n ” . Thuật toán được tiến
hành bằng cách đảo chỗ các kí tự trên YR ’ nhẳm tạo ra các AR mới với chi phí nhỏ hơn.
Với một Ar (AV, Yr ’) ta định nghĩa một phép biến đổi M(ỉ, j, 1 1 i < j < t-l) của chuỗi YR =
(yh y 2, yp) thu được sau khi loại bỏ ký tự *-■ từ Yp là phép dịch chuyển đoạn (y„
trong Yr đến vị trí t để thu được một chuỗi mới YR. Một phép biến đổi M(ỉ, j, t) được gọi
là có thể thực hiện được {possible move) nếu nó làm giảm chi phí CR của PAR mới tạo
được. Thuật toán được mô tả như sau:
Character moving method
1 Build an initial PAR Ar = (Xr Yp ’) by stepwise addition method
2 iteration 0
3 repeat
4 positionMove <— false
5 foreach triple positions (i, j, t I i <j < t-1)
6 if M(i, j, t) is a possible move then
7 Move character(yị, ,y ỷ in YR to position t
8 possibleMove <— true
9 end if
1 0
___
end fo r
________________________________________________
9
11 iteration <— iteration + 1
12 until possibleMove - false

13 return A*(Xr, Yr)
__________
Thuật toan “ simultaneous character swapping”
Thuật toán “simultaneous character moving” là một cải tiến của thuật toán “character
moving” về mặt thời gian. Một biến đổi s {k, t) được định nghĩa là phép đổi vị trí y, và y}
của chuỗi Yr. Một phép biến đổi được gọi có thể thực hiện được nếu chi phí của AR mới
giảm đi.
Xét hai phép biến đổi Si(k], tị) và s 2{k2, t2) với k; < tì, k2 < t2i kì < k2. ta nói 2 phép biến
đ ổ i n à y đ ộ c lập v ớ i nhau n ếu kỉ > t\ hoặc t2 < tj Thực n g h iệ m ch o thấy nếu ta đồng thời
thực hiện hai phép biến đổi độc lập S) và s2 có thể sẽ tạo ra 1 PAR tốt hơn. Ngược lại nếu
Si và S2 không độc lập, chỉ thực hiện phép biến đổi cho chi phí tốt hơn. Thuật toán
“simuỉaneous character swapping’ được mô tả như sau:
Simulaneous character swapping method
1 Build an initial PAR Ar = (Xr Yu') by stepwise addition method
2 iteration *— 0
3 bestCost <— 0
4 repeat
5 positionSwap *— false
6 Find independent possible swap L and sort L descendingtly
7 if \L\ > 0 then
8 t <(— \L\
9 repeat
10 swap simultaneous Lị, L, in Yff to get ỸR
Ẩr ^ A*(Xr, Yp)
12 ỉfC R(ÀfỊ) < bestCost then
13 possibleSwap <— true
14 bestCost <— Cr(Ar), Yr *— Vfi
15 else t — t/2
16 until possibleSwap - false
17 iteration «— iteration + 1

Ỉ8 until possibleSwap = true
10
19 return A (Xr, Yr)
Độ phức tạp của thuật toán “stepwise adđtion” là 0(pg3). Độ phức tạp của thuật toán
“character moving” là o {pq X i) với i là số vòng lặp. Phương pháp “simulaneous character
swapping” có độ phức tạp là Oipq X i) với i là số vòng lặp.
Trong các thuật toán ừên, thuật toán “simultaneous character swapping” cho kết quả tốt nhất
về cả thời gian và chất lượng [1].
3.4.3 Phương pháp đề xuất
Như đã trình bày ờ trên, các thuật toán hiện tại có độ phức tạp thời gian tối thiếu là o ipq*)
trong mỗi vòng lặp. Để sắp xếp được những hệ gen có kính thước vừa và lớn, chúng tôi đề
xuất phương pháp “fast swapping ", giúp giảm độ phức tạp thời gian yêu cầu trong mồi vòng
lặp xuống còn o ipq).
Ta nhận thấy, chi phí CR(AR) bao gồm hai phần: (1) chi phí sắp hàng các ký tự (chèn, xóa.
sừa) và (2) chi phí sắp xếp lại thứ tự các kí tự. Chi phí sắp xếp lại thứ tự các kí tự R-CA', Xp) +
: Ề CM-y!> . .
R(T, Yr) lớn hơn băng 0. Chi phí săp hàng giữa các ký tự C(X\ Y ’) = ỉ= 1 có thê
được tính theo phương thức quy hoạch động với độ phức tạp là Oipq).
Xét một phép đổi chỗ yi và }>J, chi phí sắp hàng có thể được ước lượng lại với độ phức tạp là
0(1) như sau:
CỌC, Y ’) - [C(*í>y'i) + C(x 'i>y'ỉ)] + [C(*Í'3Ó) + c (xj>y'i)] (4)
Trong “fast swapping” chúng ta áp dụng 2 phép đồi chỗ để tối ưu hóa chi phí CR(AR):
“single s w a p ” đ ư ợ c d ù n g đ ể tối ư u ch i p h í sắp h àn g , và "couple s w a p " đư ợ c sư d ụn g đ ề tối
ưu hóa chi phí sắp xếp lại kí tự.
“Single sw ap” là cách đổi chỗ hai ký tự bất kì của^T’ hoặc Y ’ trong khi "couple swap ” đôi
chỗ các ký tự ở cả hai chuỗi cùng một lúc. “Couple swap ” chính là thực hiện hai phép đồi
11
chỗ "single swap ” cùng lúc ứên cả hai chuỗi. Tuy nhiên tác dụng của chúng là khác nhau.
Trong k h i "single s w a p ” chủ y ế u là m th a y đ ổ i chi phí sừa ch ừ a giữ a hai chuồi thì “c o u p le
swap ” thay đổi chi phí sắp xếp lại các kí tự trong chuồi.

Một phép đổi chỗ được gọi là có thể thực hiện nếu nó làm cho chi phí CR(AR) giảm xuống.
Trong thuật toán dưới đây, đầu vào sẽ là một PAR xuất phát, chừng nào còn tìm được một
cách đổi chỗ có thể thực hiện thì ta sẽ tiến hành đổi chỗ để tìm ra PAR mới tối ma hơn. Quá
trinh này dừng lại khi không có một phép đổi chỗ có thể thực hiện nào được tìm thấy.
Fast swapping method
1
iteration <— 0
2
while (truej do
3
iteration <— iteration + I
4
fo r i - 1 to 1 X r 1 do
5
fo r j - 0 to 1 Yr \ do
6
if have possible swap s then perform s
7 if no swap performed then
8 break out o f while loop
9
Xr « - gapless(Xr ’), YR <- gapless(XR ’)
10 (XR Yr ’) <— PairwiseAiignmentfXfo Yr)
11
end while
12
return A*(Xr, Yp)
Ta nhận thấy, thời gian tính toán một phép đổi chỗ là 0 ( 1). Như vậy, dòng 4 đến dòng 7 có
độ phức tạp thời gian là o (pq). Dòng thứ 11 sử dụng thuật toán quy hoạch động để sắp hàng
hai chuỗi Xp, YR có độ phức tạp là o ipq). Như vậy độ phức tạp thời gian cùa thuật toán
“fast swapping” là o (pq X 0 với i là số lần lặp.

12
Để so sánh các phương pháp khác nhau, chúng tôi sử dụng bộ dữ liệu thật gồm 760 hệ gen tỉ
thể thu thập từ cơ sở dữ liệu sinh học quốc tế. Mỗi hệ gen chứa khoảng 16000 dna và được
chia thành khoảng 37 genes [7].
Kết quà so sánh giữa thuật toán “fast swapping” và thuật toán tốt nhất hiện tại “simultaneous
character swapping” cho thấy “fast swapping” tốt hem “simultaneous character swapping"
về cả mặt chất lượng lẫn thời gian (xem báo cáo tại phần phụ lục đề biết thêm chi tiết).
Bên cạnh dữ liệu thật, chúng tôi tiến hành so sánh các phương pháp sử dụng dữ liệu mô
phỏng. Chúng tôi cũng nhận th ấy “fast swapping” cho kết quà tốt hom “simultaneous
character swapping” về mặt chất lượng, đặc biệt “fast swapping” nhanh hơn rất nhiều
“simultaneous character swapping” (xem báo cáo tại phần phụ lục để biết thêm chi tiết).
Thí nghiệm với cả dữ liệu thật và dữ liệu mô phỏng cho thấy “Fast swapping’- tốt hơn
phương pháp tốt nhất hiện tại cả về thời gian và chất lượng.
Địa điểm, thời gian
Đề tài được tiến hành từ 6/2009 đến 6/2010 tại bộ môn KHMT, khoa CNTT. Đề tài sử
dụng máy tính và internet của bộ môn.
4. Tài liệu tham khảo
1. Le Sy Vinh, Andres Varon and Ward c. Wheeler (2006), Pairwise alignment with
rearrangements, Genome Informatics, 17(2): 141 -151.
2. Le Sy Vinh, Andres Varon, Daniel Janies and Ward c. Wheeler (2007), Towards
phylogenomic reconstruction, Proceeding of The 2007 International Conference on
Bioinformatics and Computajtional Biology, Las Vegas Nevada, USA, 98-104.
3. Andres Varon, Le Sy Vinh, Ward Wheeler (2010), POY version 4: phylogenetic
analysis using dynamic homologies, Cladistics, 26:72-85
4. Schwartz, et al. Human mouse alignments with blastz. Genome Research, 13:103—
107,2003
5. Aaron C.E., Bob Mau, Frederick R. Blattner, and Nicole T. Pema, Mauve: Multiple
Alignment of Conserved Genomic Sequence With Rearrangements, Genome Res.
2004 July; 14(7): 1394-1403
6. Brudno, M., Malde, s., Poliakov, A., Do, c. B., Couronne, o ., Dubchak, L,

Batzoglou, S. Glocal alignment: finding rearrangements during alignment.
Bioinformatics, 19:i54-i62, 2003
7. Boore, J. L. Animal mitochondrial genomes, s.l. : Oxford University Express, 1999,
Vol. 27. 1767-1780
8. Hannenhalli, s. and Pevzner, p. A., Transforming cabbage into turnip, (polynominal
algorithm for sorting signed permutations by reversals. Proceedings of the 27th
Annual ACM-SIAM Symposium on the Theory of Computing. 178-189, 1995.
9. Sankoff, D. and Blanchette, M., Multiple genome rearrangement and breakpoint
phylogeny, J. Comput. Biol., 5:555-570, 1998.
14
SUMMARY
Project Title; A new method for pairwise genome alignment with rearrangements
Code number: QC.09.03
Coordinator: Le Sy Vinh
Implementing Institution: University of Engineering and Technology
Duration: from June 2009 to June 2010.
Genome pairwise alignment with rearrangements is a new challenge in Bioinformatics.
Although several methods have been developed for this problem, they are still
computationally e x p e n siv e , and th u s im p rac tical for large ge n o m e seq u en c e s.
Scientific Results: We propose a fast and accurate algorithm (called FS) for the pairwise
genome alignment with rearrangements problem. Experiments with both metazoa
mitochondrial genomes and simulated genomes showed that FS resulted in better alignments
than other methods tested. A paper of so-called “FS: A fast algorithm for genome
Rearrangement”, is published in the proceeding of “International conference on
Bioinformatics, Computational biology, Genomics, and Chemoinformatics” from 12-
14/07/2010 in Florida, u s ( />Application: A software for researchers, specially biologists, to analyze whole genomes.
This is the first software for aligning entừe two genomes.
Education: An excellent bachelor thesis.
15
ĐẠI HỌC QƯÓC GIA HÀ NỘI

TRƯỜN G ĐẠI HỌC CÔNG NGHẸ
Hà Tuấn Cường
SẮP HÀNG HOÀN CHỈNH HAI HÊ GENOME
•
KHOÁ LUẬN TÓT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công Nghệ Thông Tin
ĐAI HỌC QUÓC GIA HA NỘI
TÍĨUNG TÂM THÔNG TIN THƯ VIÊN
CO O6 OU OO O JA-
HÀ NỘI - 2010
Lời cảm ơn
Lời đầu tiên, em xin gửi lời cảm ơn sâu sắc nhất đến thầy giáo TS. Lê Sỹ Vinh
người đã không quản vất vả tận tình h ư ớ n g dẫn em trong suốt thời gian làm khóa luận
tot nghiệp vừa qua.
Em cũng xin bày tỏ lòng biết ơn tới các thầy, cô giáo trong trường Đại học
Công nghệ - Đại học Quốc gia Hà Nội. Các thầy cô đã dạy bảo, chi dẫn chúng em và
lu ô n tạo đ iề u k iệ n tố t nh ất c h o ch ún g em h ọ c tập Trong suôt quá trình h ọc đại học.
Em cũng xin gửi lời cảm ơn tới thây giáo PGS.TS. Từ Minh Phương, người đã
cho em những ĩời khuyên bổ ích trong quá trình làm khóa luận.
Tôi cũng xin cảm ơn những người bạn của mình, các bạn đã luôn ở bên tôi,
giúp đỡ và cho tôi những ý kiến đóng góp quý báu trong học tập cũng như trong cuộc
sống.
C u ố i c ù n g c o n x in g ử i tớ i b ố m ẹ và toàn thể gia đình lòn g biết ơn và tình cảm
yêu thương nhất. Con xin dành tặng bố mẹ kết quả mà con đã đạt được trong suốt bốn
năm học đại học. Con cám ơn bố mẹ và chị nhiều.
Khóa luận được tài trợ một phần bởi đề tài nghiên cứu QC.09.03 thuộc Đại học
Quốc Gia Hà Nội.
Hà Nội, tháng 5 nãm 2010
Hà Tuấn Cường
?-n

’■puts ional Biology, G enom ic: and C he m o inforrn a tic j - M ozilfa Firefox
BCBGC is an important event in the areas of bioinformatics
computational biology, genomics and chemoinformatics and focuses on
all areas related to the conference The conference will be hew at the
same time and location where several other major international
conferences wit! be taking place. Click here for the details of these
conferences.
BCBGC is an annual event.

Forwarded message

From: PromoteResearch <>
Date: Tue, M ar16,2010 at 4:03 PM
Subject: bcbgcl45 acceptance letter
To:
Dear Colleague(s),
On b eh a lf of the committee of the 2010 Internationa! Conference on Bioinformatics,
Computational Biology, Genomics and Chemoinformatics (BCBG C -10), we are pleased to
inform you that your paper:
FS: A Fast Algorithm for Genome Rearrangements
Thang N. Dinh, PhD student
CISE Department,
University of Florida, Gainesville, FL, USA
Email:
Huan X. Hoang, Le s. Vinh
University o f Technology and Engineering
Vietnam National University, Hanoi, Vietnam
Email: huanhx0vnu. ed u . vn, vinhls@vnu■ edu . vn
paper reference number: bcbgcl45
has been accepted for oral presentation at the BCBGC-10 conference to be held in Orlando,

FL, USA during July 12-14, 2010. Congratulations! The reviewers’ comments are attached to
this email. The paper will be included in the conference proceedings provided the authors
complete all the formalities (according to the timelines) specified in this email.
The conference organizers should receive the revised and properly formatted final paper,
copyright form and the regisừation fee before April 2, 2010.
Once again, congratulations and look forward to see you in Orlando. We hope you enjoy the
event!
Sincerely
Dimitrios Karras, Zoran Majkic, MAK Sadiq
(BCBGC-10 organizing committee)
FS: A Fast Algorithm for Genome
Rearrangements
Thang N. Dinh
Department o f Computer & Information Science & Engineering
University of Florida, us

Huan X. Hoang & Le s. Vinh
University of Technology and Engineering
Vietnam National University, Hanoi, Vietnam
{huanhx, vinhls}@vnu.edu.vn
Abstract— A remarkable pattern of evolutionary is. that
• many spedes have closely related gene sequences but differ
*f dramatically in gene order. It raises a new challenge in
Maligning two genome sequences that we have to consider
• changes at both the nucleotide level and the locus level such
i as gene rearrangement, duplication or loss. Finding gene re-
V arrangements at the same time with nucleotide changes has
.’.beenformulated as a combinatorial optimization problem of
I the so-called Painvừe alignment wtíh rearrangements by Vinh
and colleagues [l]-[3]. Although several methods have been

'.'developed for this problem, they are still computationally
ị expensive. Therefore, they are impractical for large genome
i'sequences. In this paper, we propose a fast and accurate
^algorithm (called FS) for the pairwise alignment with
-rearrangements problem. Experiments with both metazoa
■mitochondrial genomes and simulated genomes showed that
ỈFS resulted in better alignments than other methods tested,
,'Moreover, it is several orders of magnitude faster than
Mother methods. FS was also integrated into an evolutionary
jframework to further improve the alignment quality.
Index Terms— Genome rearrangement, incremental algo
rithm, metazoa mitochondrial genomes, memetic algorithm
I. In t r o d u c t io n
The alignment cost between two genomes can be
used as a measure of genetic divergence between them,
besides local evolution within individual genes, genomes
also undergo large-scale events such as horizontal gene
transfer, gene rearrangement, gene duplication, gene loss
and insertion. Recent studies have showed that micro
iparrangements are abundant in genomic DNA [6, and
xferences therein]. Gene rearrangements might cause a
tomber of heritable diseases [4] [13] [20] [23]. Three
^arrangement types are inversion, ưansposition, and in
serted transposition (see Figure 1).
} Such large-scale operations enhance our understanding
0 genome alignments, thus, demand new approaches
Or aligning whole genomes. Several approaches have
èveloped for aligning the human and mouse genomes,
key were based either on local alignment [17] [22] or
n a local/global technique, in which the mouse contigs

re mapped on the human genome by a local aligner
ÚtiaUy, and then the homology is confirmed and refined
Ỷ a global aligner [10],
Pairwise genom e alignm ent m ethods such as M U M m er
[12], G LA SS [7], and W ABA [15] use the ancho r
ing techniqu e’ for the alignm ent process. The aligner
identifies a set of local alignm ents in regions of high
sim ilarity betw een two genom es, called anchors, which
are subsequently used to restrict the num ber of possible
alignm ents. A lthough these approaches are able to align
genom es with rearrangem ents, they make use of only
inform ation at the nucleo tides level. They might ignore
a large am ount of nucleotides when aligning diverged
genom es.
To obtain a com plete alignm ent between genomes,
inform ation from both nucleotide and locus levels should
be incorporated together. The genetic inform ation on the
nucleotide level (sm all-scale) includes nucleotide sub
stitution and nucleotide deletion/insertion (indel) The
genetic inform ation on the locus level (large-scale) in 
cludes character loss, ch aracter duplication, and character
rearrangem ent.
A genom e can be presen ted as a sequence o f char
acters each character p resents a gene or a segm ent
o f nucleotides. The presentation of a genom e can be
determ ined by annotations from Genbank at NCB I
(http://ww w .ncbi.nih.gov/), i.e., segments within and be
tween annotated regions. It can be also autom atically
determ ined by algorithm s such as B LA ST Z [22], Glocal
[9], or M auve [11].

T h e objective is to determ ine and align hom ologous
ch aracters betw een two genom e sequences. To this end,
we u sually use the m axim um parsimony principle, thus,
find the alignm ent w hich m inim izes the total cost to
transform one genom e to the other using operations from
both sm all-scale and large-scale levels. The total cost
consists o f two parts: the edit cost between characters
and and rearrangem ent cost betw een character orders.
The optim al pairw ise alignm ent with rearrangem ents of
two gen om es can be found by exam ining all perm utations
o f characters in genom es. However, this exact approach
is im ractable and intolerable even for small instances.
A lthough Vinh et. al. [ 1 ]—[3] have proposed some
heuristic methods, the best presented algorithm still has
high computational cost and is impractical for large
genomes.
II. P r o b l e m F o r m u l a t io n
In this section, the pairwise genome alignment with
rearrangements w ill be briefly formulated [1], We also
review current methods for this problem.
Given two genomes presented as two sequences of
characters
!
X = {X\,X2, ,xp) and Y = (yi,y2, ,yq),
where each character presents a gene or a segment of
nucleotides. .The alignment process will insert gaps into
both X and Y such that homologous characters in X and
Y are aligned. This kind of alignment is called ordinary
alignment.
* A sequence X is called a gapless sequence of X '

if X can be obtained from X ' by removing all gap
[. characters. For example X — (1,2,4,3) is a gapless
sequence of X ' = (1 / 2 ,4 / 3 / We denote the
set of gapless sequences of X by Q{X).
Formally, an alignment of a paứ of sequences (X , Y)
Ị is defined as a paừ of sequences where X' €
\ q{ X )X 6 G(Y) and \xr\ = \Y'\. The cost of an
alignment (X',Y') is defined as
I
C{X'X ) = Y j c{x'i,yli),
t i = l
I where c(xi,yj) e R+ is the edit cost to tfansform
»ch aracter Xi to ch aracter y3. F o r convenient, we also
•denote c{xi,y0) = c(xi,' -') and c(x0 lt/j) = c('-',yj)
rthe indel costs o f characters Xj and
i/j,
respectively.
The edit cost c(xi,yj) is often calculated as the edit
'dista n c e betw een tw o ch aracters X, and Uj. R ecall that
-each character is a gene or a segment of nucleotides in a
genome.
There is an infinite number of alignments of a pair of
sequences (X , Y). However, we are only interested in the
optimal ordinary alignment of (X , Y), i.e the alignment
[Xo, Y0) with the smallest cost
{X0,Y0) = argmin C(X\Y').
(x \ Y ')€ g < ,x )x g ( Y )
We also denote 0 ( x , Y) the cost of the optimal or
dinary alignment of (X , K) that can be computed using
dynamic programming technique [18] in 0(pq) time.

Denote VM{X) the set of all permutations of the
•equẹnce X . Let R(X, x r) be the rearrangement cost
?unction betw een X an d its perm utation X T e V M { X ) .
rh e reairang em ent co st R ( X , x r ) can be m easured as the
breakpoint d istan ce (the n u m ber o f c h ara c te r pairs w hich
Ịppear ill one g enom e b u t not in the other) and inversion
listance (the number of inversions needed to transform
f to X r ) [5] [14] [21]. T he bre a k p o int distance and
aversion distance is correlated, i.e., half of the number
f break p o in ts b etw een tw o gen o m es is a low er bound
f the inversion distance betw een them . B oth breakpoint
Figure ]. Three types of rearrangements on a genome ị 241
distance and inversion distance can be calculated in linear
time.
The pairwise alignm ent with rearrangem ent (PAR)
between two genom e sequences problem was defined
by Vinh and colleagues [ 1 ]—[3] where each genom e is
presented as a sequence o f characters. A PAR of tw o
sequences X and Y is a pair o f sequences
K = (x 'ỵ .x '2

x'i) and Y ' - { y [ ,y ‘2 y'l).
such that theừ gapless sequences X T and yrr are perm u
tations of X and Y , respectively. We denote V A R ị x y
the set o f all PAR o f IX , >').
The cost of a PAR A r — [X'r ,Y r ) is the sum o f edit
costs between characters and rearrangem ent costs between
character orders:
I
C(Ar[X’TX))= Y^C(x\.y'l}

1=1
+ ; R { X . X r ) - r R ( Y , Y r ) I (1)
The objective is to find an optimal PAR A ‘ =
(X ' , Y ; ) with the minim um total cost. Searching the
optim al solution by exam ining all possible PAR takes
0(p\q\ X p X q) tim e. Note that when p. q are about 20.
the required calculation w ill be out o f computing capacity
of current com puter systems.
Vinh et al. inưoduced three hill-clim bing algorithm s to
find the optimal PAR o f two genom e sequences (À*. y'l.
nam ely
Stepw ise A ddition, Character M oving and S im ul
taneous Character Sw apping [1], The general idea of
these algorithms is to start from an initial PAR, and step-
by -step im proves the current PAR by swapping characters
The swapping process is repeated for several iterations
until no im provem ent is found For each iteration, all
possible character pairs in X are exam ined if
sw apping them could reduce the total cost of the current
PAR. Am ong proposed algorithm s, Simultaneous C harac
ter Sw apping(SC S ) outperform s the others. The key tech
nique to reduce the running tim e in s c s is performing a
set o f best independent possible swaps at once. However,
s c s still has the running time of 0 ( n 4 X iteration] where
n - p + q.
III. Fa s t S w a pp in g A lg o r it h m
The bottle-neck in the S im ultaneous C haracter Sw ap
ping algorithm is that w e need 10 recalculate the total
Figure 3. Genetic algorithm. Parts marked with (*) are subjected to
changes in a Memetic approach.

Ị
! a population and individual learning in lifetimes of its
\ members. By combining global and local search, Memetic
Í Algorithms have been show n to b e ord ers o f magnitude
\ faster and more accurate than EAs on many problems.
[ The general scheme for a memetic algorithm is shown in
i Figure 3
I All individuals in the population represent local optima,
, which is ensured by ap p lying local search after gener-
Ị ating a new population by evolutionary operators. The
t algorithm is presented in Algorithm 2.
I Algorithm 2 Memetic Algorithm
■ 1: Set of population p *— 4>
2: Return the best individual in p
3: for i = 1 to popS ize do do
4:
p
<- generatePAR()
5: p *— FastSwapping(p)
I 6: p <— p u {p}
7: end for
8: while not converged do
9: Generate set o f o ffsprint c usin g C ro ssov er
•0: for ic e c do
•* ic <— FastS wapping(ic)
.12: p ^ p u {jc}
| 13: end for
'•M: Apply mutation operator on p
iJ5: p <— Selection (P)
•Jfr end while

^ Initialization
k The function generatePAR() in line 2 returns a ran-
J°wly initiated PAR of (X , V). Both X and Y are
•jtaffled and theừ ordinary alignment are found using
lynamic programming algorithm.
* Crossover
Assume that we need to combine a ‘male’ PAR
= (y?,y ?

C ))
TABLE I
Av e r a g e r e s u l t s o n m e t a z o a m t D N A g e n o m e s
Ave. Optimality
Ave. Running Time
sc s
99.39 % 0 46 s
FS
9941 9fc
0.01 s
MA
99.79 % 5 m
with a ‘fem ale’ PAR {X> = ( x { ,x f2
x { ) . y ! =
{ y ( ,y f2 y l) ) . F ưst we set (,Yc. r c ) - (Xm,y rn)
and perform coupie-sw aps on (Xc.ye) such that the
gapless sequences of x c equals to the gapless sequences
o f X 1 after swapping. By doing so, the child will inherit
the order of the sequence in the ‘fem ale’ PAR and
have the edit cost at most the edit cost of the ‘m ale’ PAR.
We create an another child in a sim ilar way with ‘m ale’

PAR in place of ‘fem ale’ PAR and vice versa.
c. M utation
The m utating is performed by applying some random
single-sw aps on the PAR. The num ber of swaps is large
enough to guarantee that the PAR will escape from the
cu ư e n t local optimum ,
V. E x p e r i m e n t a l A n a l y s i s
A. Data Sets
As no local search algorithm has a polynomial guar
antee in the worst-case, extensive testing is required.
We used two data sets: (1) a collection of 760 m etazoa
mtDNA genomes from G enbank at NCBI as used in
[1] (2) a collection o f simulated genom es with different
lengths.
M etazoa m tDNA genom es are usually found in form of
closed cứcles. They undergo no t only nucleotide transfor
mations but also gene rearrangem ents [8]. Each genome
contains about 16,000 base paks and about same 37
genes [8]. M etazoa m tDN A genom es were divided into
segm ents based on annotations from G enbank at NCBI
and each segm ent is now considered as a character. After
segm enting, a genom e has 50 characters on average. We
used the sam e testing m ethod as in [1], i.e 760 genom es
were divided random ly into 38 groups of size 20: the
PARs betw een any two genom es in the same group were
constructed.
To have sim ulated genom es, ai the first slep we ran
dom ly generated genom es. We then simulated both small-
scale and large-scale operations on genom es 10 produce
final ones. Results obtained from both real and simulated

genom es were consistent in term o f both running time
and quality o f PAR.
B. O ptim ality M easurem ent
To evaluate the optimality of a PAR í X I Y f) returned
by an algorithm , we com pared the cost of IX'r ,Y'r ) with a
t a b l e n. TABLE IE
AVERAGE RUNNING TIME ON ARTIFICIALLY GENERATED GENOMES Av e r a g e o p t i m a l it y o n a r t if i c i a l l y g e n e r a t e d g e n o m e s
Genome size
102
102.5
103
103 5
Genome size
102 1025 103
1035
scs
3.13 s
3m 29s
n/a
n/a
s c s
98.59 <* 98 46 °k n/a
nJd
FS
0.03 s
0.31 s
2.02 s
27.27 s
FS
99.07 %

99.56 % 99.82 %
99.95 %
lower bound of the optimal solution. Recall that the cost
o f the optimal solution
OPT = c(A*r(x;,Y;))
= ỊPệịi C(KX) + R{X, x r) + R(Y,Yr) }
< min{ C(X‘X) }• (3)
For a PAR (X'r,Y Ị) of (X, Y) we can add gaps into
both X'T and Y ị such that both of them have the same
length OÍ n — {p + q). Consider two sequences x + and
y + of size n
X+ = (*+ ,* + ,
K+ = (vt,yỉ, ,yị
we have
OPT < m in { C (x ;,y ;) I (x’rX ) eP % ,y ) ,
m = \y;\ = n}
= m m { ^ C ( x + ,y + (i))
•=1
I 7T is a permutation of {1,2, ,n} }
= M(X,Y) (4)
This is a linear sum assignment problem(LSAP) [19] or
minimum cost p erfect m atch in g in bipartite graph. H ence
‘the lower bound M(X,Y) can be computed in 0(n3)
ị using Kuhn-Munkres algorithm [16].
* The optimality of a PAR (X'r . Yị) with cost c r is now
! can be measured by:
m X 1 0 0% <5,
C/r
In our experiments, the transformation cost between
two characters X an d y w as c a lc u lated as the minim um

cost to change X into y usin g nu c leo tid e substitutions,
insertions, and deletions. The nucleotide substitution cost
a n d the nucleotide indel cost w ere set to 1 and 2,
respectively. T h e in del co st o f a ch a racter X or y equals
Ịo the number of its nucleotides.
The algorithm to calculate inversion distance in 0{n)
IS rather complex [5]. However, it is known from previous
work of Vinh et al. [1] that both inversion distance
tad breakpoint distance showed similar results. Thus,
we m easured rearrang e m en t co st R { X . X r ) as breakpoint
listance between X and x r.
H Tte memetic algorithm was implemented using the
JALib library, a C++ library of genetic algorithm compo-
fcnts written by Matthew Wall (
■Ịus library allows us to easily customize and combine
flth the fast swapping method.
We used Simple G A with typical parameters;
popsize 100, PcrossoveT — 0.9, Pmutation ~ 0.006
to run the algorithm through 100 generations. The result
for M A was very prom ising, however, it required a huge
amount of calculations. On metazoa mtDNA genomes, H
took m ore than 5 minutes to align a paứ of genomes.
Thus, it is not applicable to align large genom es.
Table I shows the average results on m etazoa m tDNA
genom es. Both s c s and FS obtained high optimality
ratio, however, the FS is slightly better than the s c s .
M oreover, the FS was m uch faster than s c s , i.e, about 30
tim es faster. The FS requừ ed on average only 3 iterations
to align two genom e sequences. The num ber of iterations
in case of sc s is 5 [1].

The sim ulated data set contained larger genom ic se
quences. The sizes of genom es were chosen from pow ers
o f 10. s c s was unable to align genom e sequences with
size larger ữian 102 5 due to its running time. Note that
M A is unable to align these large datasets.
B oth Tables in and II show that FS resulted in better
alignm ents than s c s . M oreover, FS is much faster lhan
than s c s . T he quadratic running time o f FS enables us to
align very large genom e sequences. Note that each char
acter in generated genom es is a sequence of 500 to 1000
nucleotides. H ence, genom es with millions of nucleotides
can be aligned in m inutes on a personal computer. All the
experiments in this section were performed on a personal
D esktop. Furthermore, table m shows that the FS gives
better optimality ratio than the s c s .
V I. C o n c l u s i o n
The Fast Sw apping (FS) algorithm results in better
PARs than the best-know n Simultaneous Swapping algo
rithm in term s o f both alignm ent quality and running time.
The s c s is only suitable for genom e sequences as
large as 100 characters whereas FS can be applied for
m ulti-thousands characters genom es that contain millions
o f base pairs. However, both algorithm s are local search
m ethods which depend heavily on initial alignm ent co n
figuration. The FS can be integrated into a global search
m ethod such as Sim ulated A nnealing, G enetic A lgorithm,
and A nt C olony to obtain even better alignment.
The proposed algorithm s were tested with breakpoint
distance as the rearrangem ent cost function. However, it
is possible to extend the algorithm s to work with other

rearrangem en t cost functions.
A c k n o w l e d g e m e n t s
This work is (partly) supported by the research project
No. QC.09.03 granted by V ietnam National University.
H anoi.
R e f e r e n c e s
[1] Vĩnh L.s, Andres Varon and Ward Wheeler, Pairwise align
ment with rearrangements, Genome Informatics 17(2) 141 -
151
[2] Varon, A., Vinh, L. s., and w . c . Wheeler, POY version 4:
phylogenetic analysis using dynamic homologies, Cladis-
tics 2010, 26:72-85.
[3] Vinh L. s , A. Varon, D. Janies, and w . c . Wheeler.
2007, Towards phylogenomic reconstruction, Proceedings
of the 2007 International Conference on Bioinformatics
and Computational Biology, Las Vegas Nevada, USA pp
98-104.
[4] Albertson DG, Collins c , McCormick F, Gray JW: Chro
mosome aberrations in solid tumors. Nat. Genet 2003
34(4):369-376. - '
[5] Bader, D.A, Moret, Bernard M.E and Yan, Mi. A Linear-
Time Algorithm for Computing Inversion Distance Be
tween Signed Permutations with an Experimental Study.
Journal o f Computational Biology, 2001, Vol. 8, pp 483-
491.
[6] Balzoglou, Serafim. The many faces of sequence align
ment. Briefings in Bioinformatics Oxford Journal, 2005,
Vol. 6.
[7] Batzoglou, S., Pachter, L., Mesirov, J, p., Berger, B-, and
Lander, E, s. (2000). Human and mouse gene structure

comparative analysis and application to exon prediction.
Genome Res, 10(7):9508.
[8] Boore, I. L. Animal mitochondrial genomes, s.l. : Oxford
University Express, 1999, Vol. 27. 1767-1780
[9] Brudno, M., Malde, s., and Poliakov, A., Do, c. B.,
Couronne, o ., Dubchak, I., and Batzoglou, s., Glo-
cal alignment: finding rearrangements during alignment,
Bioinformatics, 19:i54:i62, 2003.
[0] Couronne, o ., Poliakov, A., Bray, N., Ishkhanov, T„
Ryaboy, D., Rubin, E.M., Pachter, L., and Dubchak, I.
2003. Strategies and tools for whole genome alignments.
Genome Res. 13: 73-80.
!l] Darling, A. c ., Mau, B., Blattner, F. R-, and Pema, N.
T., Mauve: Multiple alignment o f conserved genomic se
quence with rearrangements,
Genome Res., 14:1394,1403,
2004.
2] Delcher, A, L., Kasif, s., Fleischmann, R, D„ Peterson, J.,
White, 0 ., and Salzberg, s , L. (1999). Alignment of whole
genomes. Nucleic Acids Res, 27(11):236976
3] Eichler EE, Sankoff D: Structural dynamics of eukaryotic
chromosome evolution. Science 2003, 301(5634);793-797.
4] Hannenhalli, Pevzner, p. A. Transforming cabbage into
turnip, (polynomial algorithm for sorting signed permuta
tions by reversals. Proceedings o f the 27th Annual ACM-
S1AM Symposium on the Theory o f Computing. 1995. pp.
178-189
5] Kent,w, J. and Zahler, A,M. (2000). Conservation, regu
lation, synteny, and introns in a large-scale c . briggsae-C.
elegans genomic alignment. Genome Res, 10(8): 111525.

6] Kuhn, H. w . The Hungarian method for the assignment
problem. Naval Research Logistic Quarterly, 1955, Vol. 2,
pp. 83-97
7] Ma, B., Tromp, J., and Li, M. 2002. PatternHunter: Faster
and more sensitive homology search. Bioinformatics 18:
440-445.
8] Needleman, s. B. and Wunsch, c . D. A general method
applicable to the search for similarities in the amino acid
sequence of two proteins. Journal o f Molecular Biology,
1970, Vol. 48, pp. 443-453
®] Rainer Burkard, Mauro D ell’Amico, Silvano Martello.
Assignment Problems, s .l.: SIAM Monographs on Discrete
Mathematics and Applications, pp. 75-166
®] Rieseberg L: Chromosomal rearrangements and speciation.
Trends Ecol. Evol. 2001, 16(7):351-358.
[21] Sanko, D. and Blanchette. Multiple genome rearrangement
and breakpoint phytogeny. Journal of Compui. Biol 1998.
Vol. 5, pp. 555-570
[22] Schwartz, s., Kent, W.J Smit, A Zhang, z., Baertsch. R
Hardison, R.C., Haussler, D., and Miller, w. 2003. Human-
mouse alignments with BLASTZ Genome Res 13 103-
107.
[23] Stankiewicz p, Lupski JR Genome architecture, rear
rangements and genomic disorders. Trends Genet 2002.
18(2):74-82.
[24J Wang, LiSan, et al. Distance-based genome rearrangement
phytogeny, 4, Journal o f Molecular Evolution. 2006. Vol.
63, pp. 473-83
[25] Waterston, R.H., Lindblad-Toh, K., Bimey, E., Rogers.
J., Abril, J.F., Agarwal, p Agarwala, R„ Aínscough. R

Alexandersson, M., An, p., et al. 2002. Initial sequencing
and comparative analysis of the mouse genome.
Nature
420: 520-562.